This problem has a nice BFS structure. Let's illustrate it using the example nums = [2, 3, 1, 1, 4] in the problem statement. We are initially at position 0. Then we can move at most nums[0]steps from it. So, after one move, we may reach nums[1] = 3 or nums[2] = 1. So these nodes are reachable in 1 move. From these nodes, we can further move to nums[3] = 1 and nums[4] = 4. Now you can see that the target nums[4] = 4 is reachable in 2 moves.
Putting these into codes, we keep two pointers start and end that record the current range of the starting nodes. Each time after we make a move, update start to be end + 1 and end to be the farthest index that can be reached in 1 move from the current [start, end].
To get an accepted solution, it is important to handle all the edge cases. And the following codes handle all of them in a unified way without using the unclean if statements :-)
C++
1 class Solution { 2 public: 3 int jump(vector<int>& nums) { 4 int n = nums.size(), step = 0, start = 0, end = 0; 5 while (end < n - 1) { 6 step++; 7 int maxend = end + 1; 8 for (int i = start; i <= end; i++) { 9 if (i + nums[i] >= n - 1) return step; 10 maxend = max(maxend, i + nums[i]); 11 } 12 start = end + 1; 13 end = maxend; 14 } 15 return step; 16 } 17 };
Python
1 class Solution: 2 # @param {integer[]} nums 3 # @return {integer} 4 def jump(self, nums): 5 n, start, end, step = len(nums), 0, 0, 0 6 while end < n - 1: 7 step += 1 8 maxend = end + 1 9 for i in range(start, end + 1): 10 if i + nums[i] >= n - 1: 11 return step 12 maxend = max(maxend, i + nums[i]) 13 start, end = end + 1, maxend 14 return step
