Jump Game Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg DoorDash Facebook Flipkart Google Microsoft Nutanix Oracle PayPal Salesforce Uber VMwareViews 10856

Problem Statement

Jump Game Leetcode Solution – 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:

Input 1:

nums = [2, 3, 1, 1, 4]

Output 1:

true

Input 2:

nums = [3, 2, 1, 0, 4]

Output 2:

false

Explanation for Jump Game Leetcode Solution:

i) For Input 1, we can jump 1 step from index 0 to 1, then 3 steps to the last index.

ii) For Input 2, we can try different ways but every time we will arrive at index 3. Its maximum jump length is 0. So we can’t go further from that index. So it is impossible to reach the last index.

Approach

Idea

  1. At every step, we can check what is the maximum index we can reach from that index.
  2. It’s like a greedy approach.
  3. In the end, we can check if the maximum index reached is the last index of the array.
  4. If both are the same, we can return true otherwise we can return false.

Code for Jump Game Leetcode Solution

Java Program

class Solution {
    public boolean canJump(int[] nums) {  
        int i = 0;
        for (int reach = 0; i < nums.length && i <= reach; ++i)
            reach = Math.max(i + nums[i], reach);
        return i == nums.length;
    }
}

C++ Program

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        for (int reach = 0; i < n && i <= reach; ++i)
            reach = max(i + nums[i], reach);
        return i == n;
    }
};

Complexity Analysis for Jump Game Leetcode Solution

Let N be the length of the input array.

Time complexity: O(N)

We are only iterating over the input array. So it will take O(N) time.

Space complexity: O(N)

We are using only constant space. So the space complexity is O(1).

Reference: https://en.wikipedia.org/wiki/Greedy_algorithm

Translate »