Jump Game II Leetcode Solution

In this post, we are going to solve the Jump Game II Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Table of Contents

Problem

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

Now, let’s see the leetcode solution of Jump Game II Leetcode Solution.

Jump Game II Leetcode Solution in Python

class Solution:
  def jump(self, nums: List[int]) -> int:
    ans = 0
    end = 0
    farthest = 0

    # Implicit BFS
    for i in range(len(nums) - 1):
      farthest = max(farthest, i + nums[i])
      if farthest >= len(nums) - 1:
        ans += 1
        break
      if i == end:      # Visited all the items on the current level
        ans += 1        # Increment the level
        end = farthest  # Make the queue size for the next level

    return ans

Jump Game II Leetcode Solution in CPP

class Solution {
 public:
  int jump(vector<int>& nums) {
    int ans = 0;
    int end = 0;
    int farthest = 0;

    // Implicit BFS
    for (int i = 0; i < nums.size() - 1; ++i) {
      farthest = max(farthest, i + nums[i]);
      if (farthest >= nums.size() - 1) {
        ++ans;
        break;
      }
      if (i == end) {    // Visited all the items on the current level
        ++ans;           // Increment the level
        end = farthest;  // Make the queue size for the next level
      }
    }

    return ans;
  }
};

Jump Game II Leetcode Solution in Java

class Solution {
  public int jump(int[] nums) {
    int ans = 0;
    int end = 0;
    int farthest = 0;

    // Implicit BFS
    for (int i = 0; i < nums.length - 1; ++i) {
      farthest = Math.max(farthest, i + nums[i]);
      if (farthest >= nums.length - 1) {
        ++ans;
        break;
      }
      if (i == end) {   // Visited all the items on the current level
        ++ans;          // Increment the level
        end = farthest; // Make the queue size for the next level
      }
    }

    return ans;
  }
}

Note: This problem Jump Game II is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.

NEXT: Permutations Leetcode Solution