Out of Boundary Paths (DP)
Question:
There is an m*n grid with a ball. The ball is initially at the position [start_row, start_column] . You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most max_move moves to the ball.
Given the five integers m , n, max_move , start_row , start_column , return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 10^9 + 7.
Solution:
For recursive solution, the base case would be when start_row or start_column would be either m or n respectively. In this case we return 1path. Another base case would be when max_move is 0 . In this case we return 0 path.
For the rest, we add paths of all four directions movement and decrease the max_move value by 1 for the each single movement. Then we return the sum of all the four paths.
Here’s the implementation:
def find_paths(m: int, n: int, max_move: int, start_row: int, start_column: int) -> int:
if start_row == m or start_column == n or start_row < 0 or start_column < 0:
return 1
elif max_move == 0:
return 0
else:
paths = find_paths(m, n, max_move-1, start_row-1, start_column) + \
find_paths(m, n, max_move-1, start_row+1, start_column) + \
find_paths(m, n, max_move-1, start_row, start_column-1) + \
find_paths(m, n, max_move-1, start_row, start_column+1)
return paths
m, n, max_move, start_row, start_column = 2, 2, 2, 0, 0
print(find_paths(m, n, max_move, start_row, start_column)) # prints 6
m_1, n_1, max_move_1, start_row_1, start_column_1 = 1, 3, 3, 0, 1
print(find_paths(m_1, n_1, max_move_1, start_row_1, start_column_1)) # prints 12The recursion tree for m=2, n=2, start_row=0, start_column=0, max_move=2 looks like this:
Runtime Complexity: O(4^n) where 4 is the four directions and n is the max_move .
Space Complexity: O(n) where n is the depth of the recursion.
Now let’s move to the memoized version of the implementation. Memoization helps is removing redundancy of computation by keeping cache of already computed parameters.
We are using start_row, start_column, max_move as our cache key since these parameters are the one that’s changing.
from typing import Dict, Tuple
from collections import defaultdict
def find_paths(m: int, n: int, max_move: int, start_row: int, start_column: int, memo: Dict[Tuple[int, int, int], int]) -> int:
if start_row == m or start_column == n or start_row < 0 or start_column < 0:
return 1
elif max_move == 0:
return 0
elif (start_row, start_column, max_move) in memo:
return memo[(start_row, start_column, max_move)]
else:
paths = find_paths(m, n, max_move-1, start_row-1, start_column, memo) + \
find_paths(m, n, max_move-1, start_row+1, start_column, memo) + \
find_paths(m, n, max_move-1, start_row, start_column-1, memo) + \
find_paths(m, n, max_move-1, start_row, start_column+1, memo)
memo[(start_row, start_column, max_move)] = paths
return memo[(start_row, start_column, max_move)]
memo = defaultdict(int)
m, n, max_move, start_row, start_column = 2, 2, 2, 0, 0
print(find_paths(m, n, max_move, start_row, start_column, memo)) # prints 6
memo_1 = defaultdict(int)
m_1, n_1, max_move_1, start_row_1, start_column_1 = 1, 3, 3, 0, 1
print(find_paths(m_1, n_1, max_move_1, start_row_1, start_column_1, memo_1)) # prints 12Runtime Complexity: O(m*n*N) where m is the row size, n is the column size and N is the max move.
Space Complexity: O(m*n*N) where m is the row size, n is the column size and N is the max move.
Now let’s do the Dynamic Programming (DP) implementation. Two things to remember for DP is recognizing the subproblem and using the subproblem’s solution to build the solution of the target parameters.
The subproblem is that if coordinates x,y values are outside of the grid size. In that move, we’ll add 1 to the current location else we’ll add what we had from the previous move’s location to the current location.
Here’s the implemenation:
def find_paths(m: int, n: int, max_move: int, start_row: int, start_column: int) -> int:
dp = [[[0]*n for _ in range(m)] for _ in range(max_move+1)]
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for k in range(1, max_move+1):
for i in range(m):
for j in range(n):
for d_i, d_j in dirs:
n_i, n_j = d_i+i, d_j+j
if n_i < 0 or n_i >= m or n_j < 0 or n_j >= n:
dp[k][i][j] += 1
else:
dp[k][i][j] += dp[k-1][n_i][n_j]
return dp[max_move][start_row][start_column]
m, n, max_move, start_row, start_column = 2, 2, 2, 0, 0
print(find_paths(m, n, max_move, start_row, start_column)) # prints 6
m_1, n_1, max_move_1, start_row_1, start_column_1 = 1, 3, 3, 0, 1
print(find_paths(m_1, n_1, max_move_1, start_row_1, start_column_1)) # prints 12Runtime complexity: O(k*m*n) where k is the max move allowed, m is the row size, n is the column size.
Space complexity: O(k*m*n) where k is the max move allowed, m is the row size, n is the column size.
Kudos for coming this far! 🎈
Question:
Binary Tree Right Side View
Given the root of a binary tree, imagine yourself standing on the right side of it, return the value of the nodes you can see ordered from top to bottom.
This is for practicing what question is asking.
From the diagram, it’s easy to take into account only the right node. What if the left side tree is deeper than that of right side tree? So we need to take into account both sides of the tree.
Here’s is the implementation:
from typing import Optional, List
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def right_side_view(root: Optional[TreeNode]) -> List[int]:
if root is None:
return []
q = deque([root])
res = []
while q:
size = len(q)
last_node = None
for _ in range(size):
node = q.popleft()
last_node = node
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if last_node:
res.append(last_node.val)
return res
t1 = TreeNode(1)
t1.left = TreeNode(2)
t1.right = TreeNode(3)
t1.left.right = TreeNode(5)
t1.right.right = TreeNode(4)
print(right_side_view(t1)) # prints [1, 3, 4]Runtime Complexity: O(n) where n is the tree height.
Space Complexity: O(2^n) where n is the tree height.
That is all for this post. Congratulations on learning more about algorithms! 🌻🙌
Until next time, ✨
