Last Updated: 4 Dec, 2021

Cross the river

Hard

Asked in company

Solve now

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.

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.

Solve now

Approaches

01 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)

Solve now

02 Approach

In this approach, we will use the same method as earlier and we will create a cache to not repeat the recursion steps and minimize the time complexity. Instead of storing all the positions in a set will store the positions in a map, with value as the index in the stones array.

We will create a recursive function, possiblePositions(stones, currPos, positionMap, lastStep, cache), where ‘stones’ is the array given, currPos is the current position we are checking, positionMap is the map of all positions, mapped to their index in stones array, and lastStep is the last step taken.

Algorithm:

In the possiblePositions(stones, currPos, postionSet, lastStep, cache)
- If currPos is equal to last element of stones return 1
- If currPos is not in positionMap or currPos is greater than the last element of stones or lastStep is equal to 0
  - Return 0
- If cache[currPos][lastStep] is not equal to -1, return cache[currPos][lastStep]
- Set cache[positionMap[currPos + lastStep - 1]][lastStep - 1] as possiblePosition(stones, currPos + lastStep - 1, positionMap, lastStep - 1, cache)
- Set cache[positionMap[currPos + lastStep]][lastStep] as possiblePosition(stones, currPos + lastStep, positionMap, lastStep, cache)
- Set cache[positionMap[currPos + lastStep + 1]][lastStep + 1] as possiblePosition(stones, currPos + lastStep + 1, positionMap, lastStep + 1, cache)
- If any of the above values are True return true, otherwise return False.
In the given function:
- If stones[1] - stones[0] is greater than 1
  - Return False
- Create an empty map positionMap
- Iterate pos through stones array
  - Set positionMap[pos] as index
- Return possiblePostion(stones, stones[1], positionMap, 1)

Solve now

03 Approach

In this approach, at the current step, we will try to calculate the set of all possible steps taken to reach the current step. We will create a map ‘steps’ where steps[i] is the set of all steps taken to reach ‘ith’ position.

Then for each position, we will iterate through all possible steps to get there and calculate the next steps.

Algorithm:

Create an empty set postionSet
Insert every element of stones in positionSet
Create a map with integer as key and a set as value, steps.
Insert 0 into steps[0].
Iterate pos through stones
- Iterate jump through steps[pos]
  - If jump + pos is in positionSet and jump is not equal to 0
    - Insert jump into pos
  - If jump + pos - 1 is in positionSet and jump is not equal to 1
    - Insert jump - 1 into pos
  - If jump + pos + 1 is in positionSet and jump is not equal to -1
    - Insert jump + 1into pos
If the length of the set corresponding to the last element of stones in the map steps is 0 return False, else return True.

Solve now