LeetCode 0045. Jump Game II Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

Description

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

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

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

Return the minimum number of jumps to reach index n - 1. The test cases are generated such that you can reach index 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 <= 104
• 0 <= nums[i] <= 1000
• It's guaranteed that you can reach nums[n - 1].

Solutions

Solution 1: Greedy Algorithm

We can use a variable mx to record the farthest position that can be reached from the current position, a variable last to record the position of the last jump, and a variable ans to record the number of jumps.

Next, we traverse each position i in [0,..n - 2]. For each position i, we can calculate the farthest position that can be reached from the current position through i + nums[i]. We use mx to record this farthest position, that is, mx = max(mx, i + nums[i]). Then, we check whether the current position has reached the boundary of the last jump, that is, i = last. If it has reached, then we need to make a jump, update last to mx, and increase the number of jumps ans by 1.

Finally, we return the number of jumps ans.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

Similar problems:

• 55. Jump Game
• 1024. Video Stitching
• 1326. Minimum Number of Taps to Open to Water a Garden

PythonJavaC++GoTypeScriptRustC#CPHP

class Solution: def jump(self, nums: List[int]) -> int: ans = mx = last = 0 for i, x in enumerate(nums[:-1]): mx = max(mx, i + x) if last == i: ans += 1 last = mx return ans(code-box)

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

class Solution { public: int jump(vector<int>& nums) { int ans = 0, mx = 0, last = 0; for (int i = 0; i < nums.size() - 1; ++i) { mx = max(mx, i + nums[i]); if (last == i) { ++ans; last = mx; } } return ans; } };(code-box)

func jump(nums []int) (ans int) { mx, last := 0, 0 for i, x := range nums[:len(nums)-1] { mx = max(mx, i+x) if last == i { ans++ last = mx } } return }(code-box)

function jump(nums: number[]): number { let [ans, mx, last] = [0, 0, 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; }(code-box)

impl Solution { pub fn jump(nums: Vec<i32>) -> i32 { let mut ans = 0; let mut mx = 0; let mut last = 0; for i in 0..(nums.len() - 1) { mx = mx.max(i as i32 + nums[i]); if last == i as i32 { ans += 1; last = mx; } } ans } }(code-box)

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

int jump(int* nums, int numsSize) { int ans = 0; int mx = 0; int last = 0; for (int i = 0; i < numsSize - 1; ++i) { mx = (mx > i + nums[i]) ? mx : (i + nums[i]); if (last == i) { ++ans; last = mx; } } return ans; }(code-box)

class Solution { /** * @param Integer[] $nums * @return Integer */ function jump($nums) { $ans = 0; $mx = 0; $last = 0; for ($i = 0; $i < count($nums) - 1; $i++) { $mx = max($mx, $i + $nums[$i]); if ($last == $i) { $ans++; $last = $mx; } } return $ans; } }(code-box)