Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
You can assume that you can always reach the last index.
\(O(n)\) Greedy Solution
This solution maintains three variables:
- the maximum index reachable from
i, denoted as
- the furthest we can reach within the current number of jumps, denoted as
furthest. In other words, you can go
j <= furthestin less than or equal to
- the number of jumps made so far, denoted as
i == furthest, we have to make another jump, and the furthest within that jump is the current
max_reachable is beyond the last index, then we know we can reach the last index within the next jump.
The invariant for the loop is that given the number of jumps, our jumps can reach farther than, or as far as any other jumps (
furthest holds the jumping distance). So If there is an optimal solution and the minimal jumps needed is
jumps, then we could argue that given jumps, our jumps can reach as far as the optimal solution, thus our solution is also optimal.
class Solution(object): def jump(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) <= 1: return 0 jumps = 0 furthest = 0 max_reachable = 0 for i in range(len(nums) - 1): max_reachable = max(max_reachable, i + nums[i]) if i == furthest: jumps += 1 if max_reachable >= len(nums) - 1: return jumps else: furthest = max_reachable return jumps
\(O(n^2)\) DP Solution
class Solution(object): def jump(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) <= 1: return 0 dp = [0 for _ in range(len(nums))] for i in range(len(dp) - 2, -1, -1): if i + nums[i] >= len(nums): dp[i] = 1 elif nums[i] == 0: dp[i] = float('inf') else: dp[i] = min(dp[i+1: i + nums[i] + 1]) + 1 return dp