Recursion

Downhill Turtle Release

You're given a 2D matrix height that represents the heights on a beach.

You want to find all the locations where you can release turtles so they can get to both the Bay (top and left borders of the matrix) and the River (bottom and right borders). Turtles can move downhill or on level ground, but they can't move diagonally across squares.

Return all the locations [row, col]\small \texttt{[row, col]} where you can release turtles.

Example:

=> returns [[0,0], [0,1], [0,7], [1,0], [1,1], [1,2]...]\notag \texttt{=> returns [[0,0], [0,1], [0,7], [1,0], [1,1], [1,2]...]}

Explanation: You should return all of the squares highlighted in yellow, because they have have decreasing paths to both the river and the bay.

First Few Test Cases:

To solve this problem, you can record all the possible locations where turtles can get to the Bay, and all the possible locations where turtles can get to the River. You can then return all the locations that they have in common as the solution to the problem.

First, we'll focus on just the River. We'll store whether or not each square can reach the River in a 2D matrix called river. Each entry in this matrix will be True if the square can reach the river, and False otherwise.

1. Recursion

We want to write a function that fills in the river matrix correctly. In order to do this, the idea is to start at one of the squares that touches the River.

image

We can immediately set the value of that square to True, because it obviously leads to the river - it's literally right next to it.

After we do this, we can visit all of the neighboring squares with larger values and set their values to True, because they can also reach the river. You do this recursively, until all the squares that can reach the river are set to True. Here's the recursion:

2. Base case

You don't need a base case for this recursion, because you never visit a square you've already visited. This means you never enter an infinite cycle. The recursion already checks to make sure it never visits a square that's out of bounds.

3. Code

We just wrote a function that sets elements in the river matrix equal to True if they can reach the river. You can follow the same exact process to write a function to fill in the bay matrix, and set each square equal to True if it can reach the Bay. Below, we generalized visitAll so that it works in both cases.

To code this up, first, you use the recursion to find all the squares where turtles can get to the river, and all the squares where turtles can get to the bay. You then return all of the locations that they have in common as the solution.

Here's the full code:

Time Complexity O(nm)O(nm). The total number of calls made to either river or bay is nmnm. We also have two O(nm)O(nm) for loops.

Space Complexity O(nm)O(nm). We store two n×mn\times m matrices, and a list of coordinates which can be up to n×mn \times m.

Here's a Dynamic Programming solution you can use if you're curious, where we get the answer using Tabulaton instead of doing it intuitively:

Mark as Completed:
Submits:
saveSeaWorld
Test your code to get an output here!
saveSeaWorld(
)
Test your code to get an output here!