Home » Interview Questions » Array Interview Questions » Jump Game

Jump Game


()

In jump game we have 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.

Example

Input: arr = [2,3,1,1,4]

Output: true

Input: arr = [3,2,1,0,4]

Output: false

Main idea

We will use greedy approach here. we will traverse the array the find the maximum index that we can reach if we are on any index which is less or equal to out current index.

Algorithm for Jump Game

  1. Initialize a variable max_index=0 which points to the maximum index with can reach.
  2. Initialize a variable curr_index=0 which points to the current index in the array.
  3. Iterate over the array.
  4. If the maximum index we reach from jump from curr_index which is (curr_index+ arr[ curr_index]), update max_index = curr_index + arr[ curr_index].
  5. Increment curr_index.
  6. If curr_index is less than n and max_index, repeat step 4,5,6.
  7. Check if we have reached the last index or not.

Let’s us understand it with an example:

Here the orange color points to the curr_index and blue color points to max_index

Jump Game

As our final max_index>=curr_index, so we can reach the last index.

Implementation for Jump Game

C++ Program

#include <bits/stdc++.h>
using namespace std;
/* Function to check if we can reach last index or not. */
void JumpGame(int arr[], int n)
{
    int max_index = 0; // Pointer pointing to to maximum index we can jump using the first i elements of the array.
    for (int i = 0; (i < n) and (i <= max_index); i++)
    {
        max_index = max(max_index, i + arr[i]);
    }
    if ((max_index >= (n - 1))) // Checking if we reached last index or not.
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }
    return;
}
int main()
{
    int arr[] = {2, 3, 1, 1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    JumpGame(arr, n);
    return 0;
}


true

JAVA Program

public class Main
{
    
    /* Function to check if we can reach last index or not. */
    public static void JumpGame(int arr[], int n)
    {
        int max_index = 0; // Pointer pointing to to maximum index we can jump using the first i elements of the array.
        for (int i = 0; (i < n) && (i <= max_index); i++)
        {
            max_index = Math.max(max_index, i + arr[i]);
        }
        if ((max_index >= (n - 1))) // Checking if we reached last index or not.
        {
            System.out.println("true");
        }
        else
        {
            System.out.println("false");
        }
        return;
    }
  public static void main(String[] args) {
      int n=6;
    int[] arr={3, 2, 4, 1, 3, 2};
    JumpGame(arr ,n);
  }
}
true

Complexity Analysis for Jump Game

Time Complexity

O(N)  as we are using one loop only to calculate the maximum index which can be reached from every ith index, hence in the worst case we will traverse the whole array once.

READ  Delete And Earn

Space Complexity

O(1) because here we don’t use any auxiliary space while we implement it.

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions