Unit 11 Session 1 Advanced (Click for link to problem statements)
Unit 11 Session 2 Standard (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: safety = [
[1, 2, 2, 3, 5],
[3, 2, 3, 4, 4],
[2, 4, 5, 3, 1],
[6, 7, 1, 4, 5],
[5, 1, 1, 2, 4]
]
Output: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
Explanation: These zones allow survivors to escape to both the Pacific and Atlantic Safety Zones.
EDGE CASE
Input: safety = [
[2, 1],
[1, 2]
]
Output: [[0, 0], [1, 1]]
Explanation: Zones `[0, 0]` and `[1, 1]` allow survivors to escape to both safety zones.Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For Grid Traversal problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Perform DFS starting from the Pacific and Atlantic borders separately. Track the zones reachable by each safety zone. Then, find the intersection of zones that can reach both the Pacific and Atlantic zones.
1) Define a helper function `next_moves` to get valid neighboring zones that can be moved to.
2) Define a DFS function to explore all reachable zones from a starting position.
3) Use two sets to keep track of zones reachable by the Pacific and Atlantic Safety Zones.
4) Perform DFS starting from the Pacific (top and left edges) and Atlantic (bottom and right edges).
5) Find the intersection of zones that can reach both the Pacific and Atlantic zones.
6) Return the list of zones that can escape to both safety zones.⚠️ Common Mistakes
Implement the code to solve the algorithm.
# Helper function to find valid next moves
def next_moves(position, safety, visited):
row, col = position
rows, cols = len(safety), len(safety[0])
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # Up, Down, Left, Right
valid_moves = []
for d_row, d_col in directions:
new_row, new_col = row + d_row, col + d_col
if 0 <= new_row < rows and 0 <= new_col < cols:
# Check if the next zone is less or equally safe
if safety[new_row][new_col] >= safety[row][col] and (new_row, new_col) not in visited:
valid_moves.append((new_row, new_col))
return valid_moves
# DFS function to explore all reachable zones
def dfs(row, col, safety, visited):
stack = [(row, col)]
visited.add((row, col))
while stack:
current_row, current_col = stack.pop()
for next_row, next_col in next_moves((current_row, current_col), safety, visited):
if (next_row, next_col) not in visited:
visited.add((next_row, next_col))
stack.append((next_row, next_col))
# Main function to find subzones where survivors can escape
def escape_subzones(safety):
m, n = len(safety), len(safety[0])
# Sets to track zones reachable by Pacific and Atlantic
pacific_reachable = set()
atlantic_reachable = set()
# Start DFS from Pacific border (top and left edges)
for r in range(m):
dfs(r, 0, safety, pacific_reachable) # Left edge (Pacific)
dfs(r, n - 1, safety, atlantic_reachable) # Right edge (Atlantic)
for c in range(n):
dfs(0, c, safety, pacific_reachable) # Top edge (Pacific)
dfs(m - 1, c, safety, atlantic_reachable) # Bottom edge (Atlantic)
# Collect zones that can reach both Pacific and Atlantic
result = []
for r in range(m):
for c in range(n):
if (r, c) in pacific_reachable and (r, c) in atlantic_reachable:
result.append([r, c])
return resultReview the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Example 1:
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume m is the number of rows and n is the number of columns in the grid.
O(m * n) because each cell is visited at most twice during DFS.O(m * n) due to the visited sets and the DFS stack.