GFG Minimum Number of Jumps

Problem Statement

Pattern:

---

Solution

public int jump(int[] nums){
	int limit = nums[0], jumps = 1, i = 0, n = nums.length;
	if(n == 1) return 0;
	while (i < n && i <= limit ) {
		// if end reached return jumps
		if (limit >= n - 1) return jumps;
		// find max limit in current limit
		int currLimit = limit;
		while (i <= currLimit) {
			limit = Math.max(limit, i+nums[i]);
			i++;
		}
		// if limit changed update jump
		if(limit > currLimit) jumps++;
	}
	return -1;
}

Notes

• element at current index decides the limit / how far you can jump
  • check if the limit >= num.length. if so return jumps counted. else continue
  • within the currLimit find the new max limit
  • if limit is found then it must be greater limit > currLimit. then a jump has been made, and limit has been updated

Alternative Greedy Solution