Jump Game

Companies:
  • Adobe Interview Questions
  • Amazon Interview Questions
  • Apple Interview Questions
  • Bloomberg Interview Questions
  • Facebook Interview Questions
  • Google Interview Questions
  • Nutanix Interview Questions
  • Oracle Interview Questions

Problem Statement

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Video Solution

Sample Test Cases

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.
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.

Problem Solution

In this Question we will maintain two variables ie. Curr and reachable.

So what we need to do is at any given index we will find the maximum Reachable distance and keep updating it in our reachable variable.

If at any point our current index surpasses the value in reachable then it means that we can’t reach the end of our array and we return false ( Take a look at the gif below for the first test case)

Else if we are able to Traverse the entire array this means that our current index was always less than the reachable and hence we can easily reach the end of the array. Take a look at the gif below for the 2nd test case

Complexity Analysis

Time complexity: O(n) We are doing a single pass through the nums array, hence n steps, where n is the length of the array nums.

Space complexity: O(1) We are not using any extra memory.

#include<bits/stdc++.h>
using namespace std;

bool canJump(vector<int>& nums) {
        int reachable=0;
        for(int i=0;i<nums.size();i++)
        {
            if(reachable<i)
            {
                return false;
            }
            reachable=max(reachable,i+nums[i]);
        }
        return true;
}

int main()
{
    vector<int>num;
    num.push_back(2);
    num.push_back(3);
    num.push_back(1);
    num.push_back(1);
    num.push_back(4);

    bool ans= canJump(num);

    cout<<ans;
}

 

public class Jump
{
    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;
    }

    
    public static void main(String[] args) 
    {
        Jump m = new Jump();
        int arr[] = new int[5];
        arr[0] = 2;
        arr[1] = 3;
        arr[2] = 1;
        arr[3] = 1;
        arr[4] = 4;

        System.out.println(m.canJump(arr));
        
    }
    
}

 

def canJump(nums):
    
        if len(nums) == 0:
            return False
            
        n_jumps, curr_index = 1, 0
        while n_jumps != 0:
            if curr_index == len(nums)-1:
                return True
                
            n_jumps -= 1
            n_jumps = max(nums[curr_index], n_jumps)
            curr_index += 1
        return False

arr= [2,3,1,1,4]
print(canJump(arr))

 

Scroll to Top