Escape the Infected Zone - codepath/compsci_guides GitHub Wiki
Unit 11 Session 1 Advanced (Click for link to problem statements)
Unit 11 Session 2 Standard (Click for link to problem statements)
Problem Highlights
- 💡 Difficulty: Medium
- ⏰ Time to complete: 60 mins
- 🛠️ Topics: Grid Traversal, Depth-First Search (DFS), Graph Representation
1: U-nderstand
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?
- Can survivors move diagonally?
- No, survivors can only move up, down, left, or right.
- What happens if survivors start in the middle of the grid?
- Survivors must find a path to both the Pacific and Atlantic Safety Zones by following the rules for safety levels.
- What is the meaning of ""escape""?
- Escape means that survivors can reach both the Pacific Safety Zone (top/left edges) and the Atlantic Safety Zone (bottom/right edges).
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](/codepath/compsci_guides/wiki/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](/codepath/compsci_guides/wiki/0,-0],-[1,-1)
Explanation: Zones `[0, 0]` and `[1, 1]` allow survivors to escape to both safety zones.
2: M-atch
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:
- Depth-First Search (DFS): DFS can be used to explore the grid, finding all zones reachable from the Pacific and Atlantic borders.
- Breadth-First Search (BFS): BFS could also be used, but DFS is often simpler for recursive exploration.
- Graph Representation: The grid can be represented as a graph where each zone is a node and edges exist between neighboring zones with equal or lower safety levels.
3: P-lan
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
- Forgetting to check grid boundaries during DFS.
- Failing to correctly track the visited zones for both Pacific and Atlantic DFS.
4: I-mplement
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 result
5: R-eview
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Example 1:
- 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] ]
- Expected Output: [0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], 4, 0
- Watchlist:
- Check that DFS correctly explores all reachable zones from both the Pacific and Atlantic borders.
- Verify that zones are only added to the result if they can reach both safety zones.
6: E-valuate
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.
- Time Complexity:
O(m * n)because each cell is visited at most twice during DFS. - Space Complexity:
O(m * n)due to the visited sets and the DFS stack.