[Leetcode problems] 45 Jump Game II

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.
Example:
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.
Note:
You can assume that you can always reach the last index.

At first glance, the brute force way would be exhausting all different ‘paths’ so as to count the steps. To achieve this we can adopt DFS or Dynamic Programming. However, they would get Time Limit Exceeded (TLE) error. Inspired by @Cheng_zhang, we can use Greedy to achieve O(n).

Obviously, if we jump as far as we can each time, this may not generate the optimal solution. The counter example is as following:

The reason is that, some place which is nearer than the furthest point have larger jumping powers, thus would be able to reach further in the coming move. Therefore, to adopt greedy algorithms, we may need to include the second move into consideration.

For each place, we have the reachable places as [cur,cur\_end], out of which we need to consider for the next move. In this case, we will jump to the one that would lead to the furthest point, i.e., max\{x+nums[x ] for x \in [cur,cur\_end]\}.

In the following code, cur_end is the variable used to track the reachable ranges from the current point, so that every time we reach cur_end, we would trigger another jump. fur indicates the furthest place that we can reach from the points in the reachable places.

    def jump(self, nums: List[int]) -> int:
        ret = 0
        cur_end = 0
        fur = 0
        for i in range(len(nums)-1):
            fur = max(fur,i+nums[i])
            if i == cur_end:
                ret += 1
                cur_end = fur
        return ret

Another way to implement it is to treat it as a BFS problem. i is used to loop through the array. Each time from i, we can explore its children [i,i+nums[i]], where furthest is used to track that boundary. During the exploring, cur_end tracks the boundary for its children.

class Solution:
    def jump(self, nums: List[int]) -> int:
        ret = 0
        i = cur_end = 0
        n = len(nums) - 1
        while True:
            if cur_end >= n:
                return ret
            ret += 1
            furthest = cur_end
            while i <= furthest:
                cur_end = max(cur_end,i + nums[i])
                i += 1

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments