Jump Game

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
17 upvotes
Asked in companies
OracleUberShareChat

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
4
4 4 4 4
Sample Output 1 :
YES
Explanation for Sample Output 1 :
It is YES because you can directly jump from the 1st position to the 4th position.
Sample Input 2 :
3
1 0 2
Sample Output 2 :
NO
Explanation for Sample Output 2 :
It is NO because it is impossible to reach the 3rd position.
Constraints :
1 <= N <= 10^5
1 <= JUMP[i] <= N

Time Limit = 1 sec
Hint

Check which positions you can reach starting from 0.

Approaches (1)
Optimal Dynamic Programming

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

O(N), where N is the number of points.

 

We are iterating through the points only once, so the time complexity is O(N).

Space Complexity

O(N), where N is the number of points.

 

We are using an array that can grow up to size N, so the space complexity is O(N).

Code Solution
(100% EXP penalty)
Jump Game
Full screen
Console