Implement the jumpGameMinimumJumpsGreedy method that returns the minimum number of jumps needed to reach the end.
The input array nums represents jump power at each index. From index i, you may jump up to nums[i] positions forward.
Your task is to return the minimum number of jumps needed to reach the last index from the first index.
For example, in [2,3,1,1,4], one optimal path is index 0 -> 1 -> 4, so the answer is 2.
Example 1
Input
nums (int[]) =
[2,3,1,1,4]size (int) =
5Returns (int)
2Example 2
Input
nums (int[]) =
[2,3,0,1,4]size (int) =
5Returns (int)
2Example 3
Input
nums (int[]) =
[0]size (int) =
1Returns (int)
0Use a greedy range-based approach.
Think of each jump as covering a range of reachable indexes. While scanning the current range, keep the farthest index that can be reached by the next jump. When the scan reaches the end of the current range, you must take one jump and extend the range to the farthest index found.
This gives the minimum number of jumps because each jump extends the reachable range as much as possible.
Pseudocode:
function jumpGameMinimumJumpsGreedy(nums, size):
if size <= 1:
return 0
jumps = 0
currentEnd = 0
farthest = 0
for i from 0 to size - 2:
farthest = max(farthest, i + nums[i])
if i == currentEnd:
jumps++
currentEnd = farthest
return jumpsReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run