Help Ninja to Cross River
Ninja is standing on the edge of a river and wants to cross the river. There is a wooden bridge over the river but some units of the bridge are damaged. Ninja can not step over a damaged unit of the bridge. All the safe units of the bridge are in an array/list ‘SAFE’ which is sorted in increasing order.

Ninja is currently standing on the first safe unit of the bridge and has to reach the last safe unit of the bridge by jumping.

There are some restrictions on the size of jump Ninja can make:

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.

As Ninja is warming up before crossing the bridge, he asks you for help. You need to find out whether Ninja can cross the river or not and return TRUE if Ninja can cross the river else return FALSE.

For example :

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.

Input Format:

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’.

Output format:

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

Note :

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

Constraints

1

Question

Help Ninja to Cross River

Ninja is standing on the edge of a river and wants to cross the river. There is a wooden bridge over the river but some units of the bridge are damaged. Ninja can not step over a damaged unit of the bridge. All the safe units of the bridge are in an array/list ‘SAFE’ which is sorted in increasing order.

Ninja is currently standing on the first safe unit of the bridge and has to reach the last safe unit of the bridge by jumping.

There are some restrictions on the size of jump Ninja can make:

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.

As Ninja is warming up before crossing the bridge, he asks you for help. You need to find out whether Ninja can cross the river or not and return TRUE if Ninja can cross the river else return FALSE.

For example :

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.

Example

Input Format:

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’.

Output format:

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

Note :

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

Constraints

1 <= T <=10
2 <= N <= 10^3
0 <= SAFE[i] <= 10^5

Time limit: 1 sec

Accepted Answer

Recursion

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.
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. The idea is very simple, as standing on any safe unit Ninja will always have a maximum of three choices so we will use recursion to search for all possible options.
Return the value returned by SOLVE().

Space Complexity: O(3^n)Explanation:

O(3 ^ N), where ‘N’ is the size of array/list ‘SAFE’.

This is the space used by the recursion stack to store 3 ^ N calls.

Time Complexity: O(3^n)Explanation:

O(3 ^ N), where ‘N’ is the size of array/list ‘SAFE’.

As during each call to function we are making further 3 calls thus making time complexity as O(3 ^ N).

Accepted Answer

Recursion + Memoization

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.

Space Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the size of array/list ‘SAFE’.

As we will are using a 2-D array/list of size ‘N * N’.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the size of array/list ‘SAFE’.

In the worst case, after making ‘N ^ 2' calls all the states will be explored and after that, we can directly use the result from 'MEMO'.

Java (SE 1.8)

/*
    Time Complexity: O(N ^ 2)
    Space Complexity: O(N ^ 2),

    where 'N' is the size of 'SAFE' array/list or number of safe units.
*/

import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;

public class Solution {
  private static int[][] memo;
  public static boolean solve(ArrayList safe, int index, int x, Map < Integer, Integer > myMap) {
      // Base Case.
      if (index == safe.size() - 1) {
          return true;
      }

      if (memo[index][x] != -1) {
        return (memo[index][x] == 1) ? true : false;
      }


      // Recursive Calls.
      int pos1 = safe.get(index) + x;
      int pos2 = safe.get(index) + x + 1;
      int pos3 = safe.get(index) + x - 1;

      // If pos1 is a safe unit.
      if (myMap.containsKey(pos1)) {
          if (solve(safe, myMap.get(pos1), x, myMap)) {
              memo[index][x] = 1;
              return true;
          }
      }

      // If pos2 is a safe unit.
      if (myMap.containsKey(pos2)) {
          if (solve(safe, myMap.get(pos2), x + 1, myMap)) {
              memo[index][x] = 1;
              return true;
          }
      }

      // Check if pos3 is a safe unit and x-1 is greater than 0.
      if (x - 1 > 0 && myMap.containsKey(pos3)) {
          if (solve(safe, myMap.get(pos3), x - 1, myMap)) {
              memo[index][x] = 1;
              return true;
          }
      }

      // If none of the positions lead to last safe unit return false.
      memo[index][x] = 0;
      return false;

  }

  public static boolean crossRiver(ArrayList safe) {
    int n = safe.size();

    Map < Integer, Integer > myMap = new HashMap< Integer, Integer >();
    memo = new int[n][n+1];
    // Filling memo with -1.
    for (int[] arr: memo)
    {
      Arrays.fill(arr, -1);
    }

    for (int i = 0; i < safe.size(); i++) {
        myMap.put(safe.get(i), i);
    }

    // Checking for the first safe unit.
    if (safe.get(1) - safe.get(0) == 1) {
        return solve(safe, 1, 1, myMap);
    }
    
    return false;
  }
}

Python (3.5)

'''

    Time Complexity: O(N ^ 2)

    Space Complexity: O(N ^ 2),



    where 'N' is the size of 'SAFE' array/list or number of safe units.

'''



def solve(safe, index, x, myMap):

    

    

    global memo

    # If we reached to last safe unit.

    if (index == len(safe) - 1):

        return True



    if (memo[index][x] != -1):

        return memo[index][x]



    pos1 = safe[index] + x

    pos2 = safe[index] + x + 1

    pos3 = safe[index] + x - 1



    # If pos1 is a safe unit.

    if pos1 in myMap:

        if (solve(safe, myMap[pos1], x, myMap)):

            memo[index][x] = 1

            return True



    # If pos2 is a safe unit.

    if pos2 in myMap:

        if (solve(safe, myMap[pos2], x + 1, myMap)):

            memo[index][x] = 1

            return True



    # Check if pos3 is a safe unit and x-1 is greater than 0.

    if (x - 1 > 0):

        if pos3 in myMap:

            if (solve(safe, myMap[pos3], x - 1, myMap)):

                memo[index][x] = 1

                return True



    # If none of the positions lead to last safe unit return false.

    memo[index][x] = 0

    return False



def crossRiver(safe):

    

    global memo

    n = len(safe)



    myMap = dict()

    

    memo = [[-1 for j in range(n + 1)] for i in range(n)]



    for i in range(n):

        myMap[safe[i]] = i



    # Checking for the first safe unit.

    if (safe[1] - safe[0] == 1):

        return solve(safe, 1, 1, myMap)



    return False

C++ (g++ 5.4)

/*
    Time Complexity: O(N ^ 2)
    Space Complexity: O(N ^ 2),

    where 'N' is the size of 'SAFE' array/list or number of safe units.
*/

#include

vector < vector < int >> memo;

bool solve(vector < int > & safe, int index, int x, unordered_map < int, int > & myMap) {
    // If we reached to last safe unit.
    if (index == safe.size() - 1) {
        return true;
    }

    if (memo[index][x] != -1) {
        return memo[index][x];
    }

    int pos1 = safe[index] + x;
    int pos2 = safe[index] + x + 1;
    int pos3 = safe[index] + x - 1;

    // If pos1 is a safe unit.
    if (myMap.find(pos1) != myMap.end()) {
        if (solve(safe, myMap[pos1], x, myMap)) {
            memo[index][x] = 1;
            return true;
        }
    }

    // If pos2 is a safe unit.
    if (myMap.find(pos2) != myMap.end()) {
        if (solve(safe, myMap[pos2], x + 1, myMap)) {
            memo[index][x] = 1;
            return true;
        }
    }

    // Check if pos3 is a safe unit and x-1 is greater than 0.
    if (x - 1 > 0 and myMap.find(pos3) != myMap.end()) {
        if (solve(safe, myMap[pos3], x - 1, myMap)) {
            memo[index][x] = 1;
            return true;
        }
    }

    // If none of the positions lead to last safe unit return false.
    memo[index][x] = 0;
    return false;

}

bool crossRiver(vector < int > & safe) {
    int n = safe.size();

    unordered_map < int, int > myMap;
    memo = vector < vector < int >> (n, vector < int > (n + 1, -1));

    for (int i = 0; i < safe.size(); i++) {
        myMap[safe[i]] = i;
    }

    // Checking for the first safe unit.
    if (safe[1] - safe[0] == 1) {
        return solve(safe, 1, 1, myMap);
    }

    return false;
    
}

Accepted Answer

Bottom-Up DP

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.

Space Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the size of array/list ‘SAFE’.

As we will are using a 2-D array/list ‘DP’ of size ‘N * N’.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the size of array/list ‘SAFE’.

As we are running two nested loops.

Python (3.5)

'''

    Time Complexity: O(N ^ 2)

    Space Complexity: O(N ^ 2),



    where 'N' is the size of 'SAFE' array/list or number of safe units.

'''



def crossRiver(safe):

    n = len(safe)

    dp = [[0 for j in range(n + 1)] for i in range(n)]



    # As the first step will be of size 1.

    dp[0][1] = True



    for i in range(1, n):

        for j in range(i):

            diff = safe[i] - safe[j]

            if (diff < 0 or diff > n or dp[j][diff] == False):

                continue

            

            dp[i][diff] = True

            if (diff - 1 >= 0):

                dp[i][diff - 1] = True

            

            if (diff + 1 <= n):

                dp[i][diff + 1] = True



            # If dp[i][j] is true for any j return true.

            if (i == n - 1):

                return True



    return False

Java (SE 1.8)

/*
    Time Complexity: O(N ^ 2)
    Space Complexity: O(N ^ 2),

    where 'N' is the size of 'SAFE' array/list or number of safe units.
*/
    
import java.util.ArrayList;

public class Solution {
  public static boolean crossRiver(ArrayList safe) {
    int n = safe.size();
    boolean [][] dp = new boolean[n][n+1];

    // As the first step will be of size 1.
    dp[0][1] = true;

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            int diff = safe.get(i) - safe.get(j);
            if (diff < 0 || diff > n || dp[j][diff] == false) {
                continue;
            }

            dp[i][diff] = true;
            if (diff - 1 >= 0) {
                dp[i][diff - 1] = true;
            }
            
            if (diff + 1 <= n) {
                dp[i][diff + 1] = true;
            }

            // If dp[i][j] is true for any j return true.
            if (i == n - 1) {
                return true;
            }

        }
    }

    return false;
  }
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N ^ 2)
    Space Complexity: O(N ^ 2),

    where 'N' is the size of 'SAFE' array/list or number of safe units.
*/

bool crossRiver(vector < int > & safe) {
    int n = safe.size();
    vector < vector < bool >> dp(n, vector < bool > (n + 1, 0));

    // As the first step will be of size 1.
    dp[0][1] = true;

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            int diff = safe[i] - safe[j];
            if (diff < 0 or diff > n or dp[j][diff] == false) {
                continue;
            }
            dp[i][diff] = true;
            if (diff - 1 >= 0) {
                dp[i][diff - 1] = true;
            }
            if (diff + 1 <= n) {
                dp[i][diff + 1] = true;
            }

            // If dp[i][j] is true for any j return true.
            if (i == n - 1) {
                return true;
            }

        }
    }

    return false;
}

Ninja is currently standing on the first safe unit of the bridge and has to reach the last safe unit of the bridge by jumping.

There are some restrictions on the size of jump Ninja can make:

As Ninja is warming up before crossing the bridge, he asks you for help. You need to find out whether Ninja can cross the river or not and return TRUE if Ninja can cross the river else return FALSE.

For example :

Input Format:

Output format:

Note :

Constraints

Top ThoughtWorks Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in ThoughtWorks Software Developer