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

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.

Space Complexity

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