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] where you can release turtles.
Example:
Explanation: You should return all of the squares highlighted in yellow, because they have have decreasing paths to both the river and the bay.
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.
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). The total number of calls made to either river
or bay
is nm. We also have two O(nm) for loops.
Space Complexity O(nm). We store two n×m matrices, and a list of coordinates which can be up to n×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:
We'll just focus on the Dolphin River at first. We want a function that computes whether or not we can get to Dolphin River from a square.
1. Recursion
A square can get to Dolphin River if any of its neighbors which are the same height or lower than it can get there:
2. Base case
All the squares touching Dolphin River can get there. That's our base case.
3. Code
Tabulation is when we compute canGetToDolphinRiver
in the order it's needed. This means the base case, then anything that depends on the base case, and so on.
We can just set the base cases to true, then the squares that can get to the Dolphin River using them to true, and so on. This is just Tabulation. You usually see Tabulation as iterative, and this is recursive, but it's Tabulation regardless. Here's the code:
setTrue
is the same exact code that we wrote for visitAll
when filling in the entries of the river matrix above. If you continue with this and do the same thing for the bay, you'll reconstruct the same exact solution that we had above.
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()