Cross the river

Hard
0/120
profile
Contributed by
6 upvotes
Asked in company
Salesforce

Problem statement

You have to cross a river, and there are several stones across the length of the river. You are given an array of ‘stones’ representing the distance of each stone from your side of the river. Your task is to reach from stone at position 0 to the last stone. If the last jump was ‘x’ units, the next jump could be either ‘x’, ‘x + 1’ or ‘x - 1’ units. The ‘stones’ array will be in ascending order.

Note: 
Assume the first jump to be 1 unit.

You can jump only on a stone.
For example: 
You are given ‘stones’ = [0, 1, 3, 5], in this array you can go from 0 -> 1 (1 unit), then from 1 -> 3 (2 units), 3 -> 5 (2 units). Hence the answer is True.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ representing the size of the array.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.
Output Format: 
For each test case, return True if you can reach the last stone, else return False.

Print a separate line for each test case.
Constraints:
1 <= T <= 10
2 <= N <= 10^3
1 <= stones[i] <= 10^9
stones[0] = 0

Time Limit: 1 sec.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1:
2
4
0 1 3 5
5
0 1 3 6 7
Sample Output 1:
True
False
Explanation:
For the first test case, ‘stones’ = [0, 1, 3, 5], in this array you can go from 0 -> 1 (1 unit), then from 1 -> 3 (2 units), 3 -> 5 (2 units). Hence the answer is True.

For the second test, ‘stones’ = [0, 1, 3, 6, 7], in this array you can go from 0 -> 1 (1 unit), then from 1 -> 3 (2 units), 3 -> 6 (3 units). Then possible moves are of length 3, 4 or 2, but none of the moves can reach 7 from 6. Hence the answer is False.
Sample Input 2:
2
4
1 3 5 6
3
1 2 3
Sample Output 2:
False
True
Hint

Try every possible path recursively.

Approaches (3)
Recursive Approach

In this approach, at each step, we will keep track of the last step taken and try all possible next steps. If any of the steps return true, then the current step will also return true.

We create a set postionSet to check if the current position is present in the stones array.

We will create a recursive function, possiblePositions(stones, currPos, positionSet, lastStep), where ‘stones’ is the array given, currPos is the current position we are checking,  positionSet is the set of all positions, and lastStep is the last step taken.

 

Algorithm:

  • In the function possiblePositions(stones, currPos, positionSet, lastStep)
    • If currPos is equal to last element of stones return True
    • If currPos is not in positionSet or currPos is greater than the last element of stones or lastStep is equal to 0
      • Return False
    • Set ans as possiblePosition(stones, currPos + lastStep - 1, positionSet, lastStep) or possiblePosition(stones, currPos + lastStep, positionSet, lastStep) or possiblePosition(stones, currPos + lastStep + 1, positionSet, lastStep)
    • Return ans
  • In the given function
    • If stones[1] - stones[0] is greater than 1
      • Return False
    • Create an empty set postionSet
    • Insert every element of stones in positionSet
    • Return possiblePostion(stones, stones[0], positionSet, 1)
Time Complexity

O(3^N), Where N is the size of the array.

 

At each recursion step, we are calling the function 3 times. Hence there will be a total of 3^N calls. Hence the final time complexity is O(3^N).

Space Complexity

O(N), Where N is the size of the array.

 

The recursion stack and the set will both take O(N) space. Hence the final space complexity is O(N).

Code Solution
(100% EXP penalty)
Cross the river
Full screen
Console