Jump Game LeetCode Solution

Last updated on January 19th, 2025 at 05:53 pm

Here, we see a Jump Game LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Greedy

Companies

Microsoft

Level of Question

Medium

Jump Game LeetCode Solution

Jump Game LeetCode Solution

1. Problem Statement

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Greedy Algorithm. The problem is solved by making a series of locally optimal choices (e.g., determining the farthest reachable index at each step) to achieve the globally optimal solution (determining if the last index is reachable).

3. Code Implementation in Different Languages

3.1 Jump Game C++

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int i, minjump = 0;
        for(i = nums.size()-2; i >= 0; i--){
            minjump++;
            if(nums[i] >= minjump)
			    minjump = 0;
        }
        if(minjump == 0) 
		    return true;
        else 
		    return false;        
    }
};

3.2 Jump Game Java

class Solution {
    public boolean canJump(int[] nums) {
       if(nums.length < 2) return true;
       
       for(int curr = nums.length-2; curr>=0;curr--){
           if(nums[curr] == 0){
               int neededJumps = 1;
               while(neededJumps > nums[curr]){
                   neededJumps++;
                   curr--;
                   if(curr < 0) return false;
               }
           }
       }
       return true;        
    }
}

3.3 Jump Game JavaScript

var canJump = function(nums) {
  let idx = 0;
  let max = 0;
  let target = nums.length - 1;
  while(idx < nums.length) {
    max = Math.max(max, idx + nums[idx]);
    if (max >= target) {
      return true;
    }
    if (max <= idx && nums[idx] === 0) {
      return false;
    }
    idx++;
  }
  return false; 
};

3.4 Jump Game Python

class Solution(object):
    def canJump(self, nums):
        max_reach, n = 0, len(nums)
        for i, x in enumerate(nums):
            if max_reach < i: return False
            if max_reach >= n - 1: return True
            max_reach = max(max_reach, i + x)

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n)O(1)
JavaO(n)O(1)
JavaScriptO(n)O(1)
PythonO(n)O(1)

Scroll to Top