Question

Formatted question description: https://leetcode.ca/all/45.html

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and
i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [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.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 1000
It's guaranteed that you can reach nums[n - 1].

Algorithm

To solve this problem, we can use the Greedy algorithm. The idea is to determine the farthest range that can be reached from the current position. We need to keep track of two variables, cur and pre, which represent the farthest position that can be reached from the current position and the farthest position that can be reached from the previous position, respectively.

Starting from the first position, we traverse all the positions that can be reached by the current jump. We then predict the farthest distance that can be jumped in the next step according to the jump force at that position and update cur to be the maximum of its current value and i + A[i].

If the current position i is less than or equal to pre, it means that it is still within the range that the previous jump can reach. Therefore, we can update cur as described above. If cur is still less than or equal to i, it means that we cannot go any further, and we should return -1.

If cur reaches the last position, we can return the number of steps used so far, which is the minimum number of steps required to reach the end. Otherwise, we update pre to be the same as cur and repeat the process until we reach the end or determine that it cannot be reached.

Therefore, the time complexity of this algorithm is O(n), where n is the length of the input array, and the space complexity is O(1), as we only need to store two variables.

Code

Java

This one is easier to understand, with the break; check

public class Solution {

	public int jump(int[] A) {
		int jumps = 0, curEnd = 0, curFarthest = 0;
		for (int i = 0; i < A.length - 1; i++) { // @note: i < Len - 1. 也就是停在倒数第二个
			curFarthest = Math.max(curFarthest, i + A[i]);
			if (i == curEnd) {
				jumps++;
				curEnd = curFarthest;

				if (curEnd >= A.length - 1) {
					break;
				}
			}
		}
		return jumps;
	}
}



public class Jump_Game_II {

	class Solution {
        public int jump(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }

            int left = 0; // last jump reaching to
            int right = 0; // current jump reaching to

            int count = 0;

            for (int i = 0; i < nums.length - 1; i++) { // @note: i < Len - 1. 也就是停在倒数第二个
                right = Math.max(right, i + nums[i]);
                if (i == left) { // reaching furthest of last jump
                    count++;
                    left = right;

                    if (curEnd >= A.length - 1) {
                      break;
                    }
                }
            }

            return count;
        }
    }
}

############

class Solution {
    public int jump(int[] nums) {
        int end = 0;
        int mx = 0;
        int steps = 0;
        for (int i = 0; i < nums.length - 1; ++i) {
            mx = Math.max(mx, i + nums[i]);
            if (i == end) {
                end = mx;
                ++steps;
            }
        }
        return steps;
    }
}

// OJ: https://leetcode.com/problems/jump-game-ii/
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
    int jump(vector<int>& A) {
        int N = A.size();
        vector<int> dp(N, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 1; j <= A[i] && i + j < N; ++j) {
                dp[i + j] = min(dp[i + j], 1 + dp[i]);
            }
        }
        return dp[N - 1];
    }
};

class Solution:
    def jump(self, nums: List[int]) -> int:
        current_reach = next_reach = steps = 0
         # stop at 2nd-to-last, not the last index. because, eg. nums=[1,0] or nums=[0,0], just check the 2nd-to-last then we can decide if able to reach end
        for i, num in enumerate(nums[:-1]):
            next_reach = max(next_reach, i + num)
            if i == current_reach:
                current_reach = next_reach
                steps += 1 # in question, guarenteed can reach end. or else need more check
        return steps

############

class Solution(object):
  def jump(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    pos = 0
    ans = 0
    bound = len(nums)
    while pos < len(nums) - 1:
      dis = nums[pos]
      farthest = posToFarthest = 0
      for i in range(pos + 1, min(pos + dis + 1, bound)):
        canReach = i + nums[i]
        if i == len(nums) - 1:
          return ans + 1
        if canReach > farthest:
          farthest = canReach
          posToFarthest = i
      ans += 1
      pos = posToFarthest
    return ans

func jump(nums []int) int {
	mx, steps, end := 0, 0, 0
	for i := 0; i < len(nums)-1; i++ {
		mx = max(mx, i+nums[i])
		if i == end {
			end = mx
			steps++
		}
	}
	return steps
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

public class Solution {
    public int Jump(int[] nums) {
        int end = 0;
        int mx = 0;
        int steps = 0;
        for (int i = 0; i < nums.Length - 1; ++i)
        {
            mx = Math.Max(mx, i + nums[i]);
            if (i == end)
            {
                end = mx;
                ++steps;
            }
        }
        return steps;
    }
}

impl Solution {
    pub fn jump(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut dp = vec![i32::MAX; n];
        dp[0] = 0;
        for i in 0..n - 1 {
            for j in 1..=nums[i] as usize {
                if i + j >= n {
                    break;
                }
                dp[i + j] = dp[i + j].min(dp[i] + 1);
            }
        }
        dp[n - 1]
    }
}

function jump(nums: number[]): number {
    let ans = 0;
    let mx = 0;
    let last = 0;
    for (let i = 0; i < nums.length - 1; ++i) {
        mx = Math.max(mx, i + nums[i]);
        if (last === i) {
            ++ans;
            last = mx;
        }
    }
    return ans;
}

45 - Jump Game II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions