Zombie Infested City Regions - 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: 45 mins
  • 🛠️ Topics: Grid Traversal, Depth-First Search (DFS)

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?
  • How do fences split the grid?
    • A / splits the square diagonally from the top-right to the bottom-left.
    • A \ splits the square diagonally from the top-left to the bottom-right.
  • How is the grid expanded?
    • Each square in the grid is split into 3x3 smaller cells for easier region tracking.
HAPPY CASE
Input: grid = [""/ "", ""/ ""]
Output: 2
Explanation: The fences split the grid into two distinct regions.

EDGE CASE
Input: grid = ["" ""]
Output: 1
Explanation: The grid has no fences, so the entire area is one region.

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 is used to explore the grid, marking visited regions.
  • Connected Components: Each region in the grid is a connected component of open cells.
  • Graph Representation: The grid can be treated as a graph where each smaller 1x1 area represents a node, and edges exist between adjacent open areas.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Each grid cell can be expanded into a 3x3 subgrid. A / fence splits the top-right to bottom-left, and a \ fence splits the top-left to bottom-right. Use DFS to explore and count the number of distinct regions in this expanded grid.

1) Expand the grid into a 3x3 representation.
    - For `/`, mark the diagonal from top-right to bottom-left.
    - For `\`, mark the diagonal from top-left to bottom-right.
2) Use DFS to explore unvisited cells and mark the entire region as visited.
3) Count the number of distinct regions by running DFS on each unvisited cell.
4) Return the total number of regions.

⚠️ Common Mistakes

  • Forgetting to check grid boundaries during DFS.
  • Misinterpreting how fences split the grid into regions.

4: I-mplement

Implement the code to solve the algorithm.

# Helper function to find valid next moves
def next_moves(position, visited, n):
    row, col = position
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # Up, Down, Left, Right
    valid_moves = []
    
    # Explore in all 4 directions
    for d_row, d_col in directions:
        new_row, new_col = row + d_row, col + d_col
        if 0 <= new_row < n * 3 and 0 <= new_col < n * 3 and not visited[new_row][new_col]:
            valid_moves.append((new_row, new_col))
    
    return valid_moves

# DFS function to mark the entire region as visited
def dfs(position, visited, n):
    stack = [position]
    while stack:
        row, col = stack.pop()
        if not visited[row][col]:
            visited[row][col] = True
            # Add valid next moves to the stack
            stack.extend(next_moves((row, col), visited, n))

# Main function to count regions
def count_regions(grid):
    n = len(grid)
    visited = [[False] * (n * 3) for _ in range(n * 3)]
    
    # Convert the grid into a 3x3 representation
    for i in range(n):
        for j in range(n):
            if grid[i][j] == '/':
                visited[i * 3][j * 3 + 2] = True
                visited[i * 3 + 1][j * 3 + 1] = True
                visited[i * 3 + 2][j * 3] = True
            elif grid[i][j] == '\\':
                visited[i * 3][j * 3] = True
                visited[i * 3 + 1][j * 3 + 1] = True
                visited[i * 3 + 2][j * 3 + 2] = True
    
    # Count the number of regions using DFS
    regions = 0
    for r in range(n * 3):
        for c in range(n * 3):
            if not visited[r][c]:
                dfs((r, c), visited, n)
                regions += 1
    
    return regions

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: grid = [""/ "", ""/ ""]
  • Expected Output: 2
  • Watchlist:
    • Ensure that all fences are correctly marked in the expanded 3x3 grid.
    • Verify that DFS is marking entire regions as visited.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the size of the original grid.

  • Time Complexity: O(n^2) because each cell in the expanded 3x3 grid is visited once.
  • Space Complexity: O(n^2) due to the expanded 3x3 grid and the visited array.