Difficulty: Hard
Category: Dynamic Programming
Step 1: Grasping the Problem
Many people classify this popular “Minimum number of jumps” problem into a dynamic programming problem. In spite of it being truely a dynamic programming problem, it can be solved without noticing any dynamic programming behavior in it. The problem will give you a nonnegative integer array nums
, where each element defines the maximum length of jump one can make from that index. Starting from index 0
, you need to determine the minimum number of jumps required to reach the end of the array.
Below are some important inference one might miss from this problem.
 Although the problem does not say anything whether you can jump backward or not, it is not necessary because each element of the array represents maximum jump length. That means of course, you can make shorter jumps in order to get the best result.
 From an element, the farthest point we can go will never decrease for the forthcoming elements. So if we are at
i
th stair and the farthest stair we could go isfarthest_possible
,farthest_possible
will always increase fori+k
wherek
isnumsi
.  We do not need the last value of
nums
. Because we will never jump from the last index (it is the destination).
Step 2: Keep track of farthest stair possible
We can start iterating through nums
and keep track of the farthest stair we can go from any previous index. For index i
, it will be max(k + nums[k])
where k = 0:i
. We will also initialize a variable names total_jumps
to store the result. Notice how we are leaving the last index of the array in the loop.


Step 3: Keep track of last jump end
When we reach at a stair which is farthest from the last jump we made, we need to make a new jump. And this jump is not necessarily needed to make from the current index. We can make a jump from any stair before (preferably from that stair which will send us to the farthest_possible).
But as soon as we make a jump, we need to keep track of the farthest jump during that time (let this stored variable be current_end
). Next time at each index, we will check if we have reached the end of the last jump or not.


The visualization of how farthest_possible
, current_end
and total_jumps
work is demonstrated below.
Step 4: Return the total jumps
After the iteration ends, total_jumps
will hold the total jumps needed to reach the last index.


We are assuming that it is guaranteed to reach the end of the array. But it is pretty easy to handle, just check if farthest_possible
is less than jump_ind
.
This algorithm runs only a single loop, so it takes O(n)
time and O(1)
space complexity. The complete program is given below.





