New update is available. Click here to update.

Last Updated: 14 Mar, 2021

Difficulty: Hard

```
1. The first jump will always be of 1 unit.
2. If Ninja's previous jump was ‘X’ units, his current jump must be either ‘X’ - 1, ‘X’, or ‘X’ + 1 units.
```

```
If ‘SAFE’ = [1, 2, 4, 7] then it can shown in below image where :
Red cell means that the unit is damaged.
Green cell means that the unit is safe.
We can see Ninja can reach the last unit by making jumps of size 1 , 2 and 3.
```

```
The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of each test case contains a single integer ‘N’ denoting the size of ‘SAFE’ or we can say the number of safe units.
The second line contains ‘N’ space-separated distinct integers denoting the elements of ‘SAFE’.
```

```
For each test case return, true if Ninja can cross the river else return false.
```

```
You don’t have to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <=10
2 <= N <= 10^3
0 <= SAFE[i] <= 10^5
Time limit: 1 sec
```

**Complete Algorithm:**

- First of all, we will make a HashMap say ‘MY_MAP’ to store safe units where the key will be ‘SAFE[i]’ and the value will be ‘i’.
- We will make a helper recursive function named ‘
**SOLVE’**which will receive 4 parameters ‘SAFE’, ‘MY_MAP’, index of current unit ‘INDEX’ and size of previous jump ‘X’. - Base Case:
- If ‘INDEX’ is equal to last safe unit:
- Return true.

- If ‘INDEX’ is equal to last safe unit:
- Recursive Calls:
- Now we have three possible places to go :
- ‘POS1’ = ‘SAFE[INDEX]’ + ’X’.
- ‘POS2’ = ‘SAFE[INDEX]’ + ‘X’ - 1.
- ‘POS3’ = ‘SAFE[INDEX]’ + ‘X’ +1.

- If “POS1’ exists in ‘MY_MAP’ then do:
- Make a recursive call with ‘INDEX’ as ‘MY_MAP[POS1]’ and keep ‘X’ the same.

- Similarly, we will check for ‘POS2’ and ‘POS3’.
- If the recursive call returns true for any of these three we will return true.

- Now we have three possible places to go :
- Return the value returned by
**SOLVE()**.

Our last approach was very simple and easy, but its time complexity was of exponential order. We can improve our solution by taking care of the overlapping subproblems. Thus, we will eliminate the need for solving the same subproblems again and again by storing them in a lookup table. This approach is known as Memoization.

We will initialize a 2-D array say MEMO [N][N + 1] with -1, where N is the size of ‘SAFE’. MEMO[i][j] equals to -1 means the current state is not explored. Otherwise, MEMO[i][j] will store whether it is possible to cross the river if Ninja is standing on ‘i’th safe unit with a previous jump of size ‘j’.

So there will be two modification to the earlier approach :

- In the Base Case, first of all, we will check the value of MEMO. If it is not equal to -1, then simply return the value stored in the MEMO.
- In Recursive Calls, before returning the true or false, we will store the value in MEMO.

Our earlier approach (recursion with memoization) surely avoided some subproblems but we can still improve time complexity using a bottom-up approach. So we will make a 2-D array say DP where DP[i][j] denotes that standing at safe unit ‘i’, whether Ninja can make a jump of size ‘j’ or not.

**Recurrence relation :**

- If ‘i’ and ‘j’ are two safe units such that ‘j’ < ’i’ then :
- Say ‘DIST’ = ‘SAFE[i]’ - ‘SAFE[j]’
- if DP[j][DIST] is true then do:
- Set DP[i][DIST - 1] = true.
- Set DP[i][DIST] = true.
- Set DP[i][DIST + 1] = true.

So if DP[N - 1][j] is true for any value of ‘j’ we will return true else we return false.

SIMILAR PROBLEMS

Randomly Sorted

Posted: 13 Nov, 2022

Difficulty: Moderate

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

8-Queen Problem

Posted: 19 Dec, 2022

Difficulty: Easy

Popular Interview Problems: