Last Updated: 4 Dec, 2021

Jump Game

Moderate

Asked in companies

Solve now

Problem statement

There is an array 'JUMP' of size 'N' which is 1-indexed and you are currently at index 1. Your goal is to reach index 'N' (end).

When you are at index 'i', you can jump a maximum length of 'JUMP[i]' which means you can make a jump of size 1 to JUMP[i]. Return true if you can reach the end otherwise false.

Example:-

N = 5
JUMP = [1,2,3,4,5]

ANSWER:- The answer should be YES as you can jump from 1st index to 2nd index, from 2nd index to 4th index, and from 4th index to 5th index.

Input Format :

The first line contains an integer ‘N’ denoting the length of the array 'JUMP'.

The second line contains ‘N’ integers which denote values of 'JUMP'.

Output Format :

"YES" is printed if the function returns true, otherwise "NO".

Note :

You are not required to print anything, it has already been taken care of. Just implement the function.

Solve now

Approaches

01 Approach

Use Dynamic Programming to find out the position you can reach. If you can reach the last position return True, else return False. A position i is reachable if DP[j] is 1 and j+JUMP[j] is greater than equal to i. Instead of updating the full range that can be reached from position i, mark the starting and ending points that can be reached from the ith position.

Algorithm:-

Initialize an empty DP array with 0 of length N plus 1.
Update DP[0] with 1.
Update DP[1] with -1.
Iterate from 0 to N (Let’s say the iterator is i).
- If DP[i] is 1,
  - Update DP[j] to DP[j] plus 1,
  - If j+JUMP[i]+1 is less than equal to n,
    - Update DP[j+JUMP[i]+1] to DP[j+JUMP[i]+1] minus 1.
  - Else,
    - Update DP[N] to DP[N] minus 1.
- Update DP[i+1] as DP[i+1] plus DP[i].
If DP[N-1] is greater than 0, return True, else return False.

Solve now