Zombie Spread - codepath/compsci_guides GitHub Wiki

Unit 11 Session 1 Standard (Click for link to problem statements)

Unit 11 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 45 mins
  • 🛠️ Topics: Grid Traversal, Breadth-First Search, Queue

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 does the infection spread?
    • The infection spreads from infected zones (2s) to adjacent safe zones (1s) in one hour.
  • Can infection spread diagonally?
    • No, infection only spreads horizontally and vertically.
  • What should be returned if there are no safe zones?
    • Return 0 since there is nothing to infect.
  • What happens if there are unreachable safe zones?
    • If any safe zones remain after all possible infections, return -1.
HAPPY CASE
Input: grid = [
    [2,1,1],
    [1,1,0],
    [0,1,1]
]
Output: 4
Explanation: The infection spreads through the entire city in 4 hours.

EDGE CASE
Input: grid = [
    [2,1,1],
    [0,1,1],
    [1,0,1]
]
Output: -1
Explanation: The safe zone at (2, 0) cannot be infected as it is blocked by obstacles.

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:

  • Graph Representation: Each cell in the grid is a node, and edges exist between adjacent safe zones (1s) and infected zones (2s).
  • Breadth-First Search (BFS): Use BFS to simulate the spread of infection from multiple sources (initial infected zones).
  • Queue: A queue is used to store the positions of infected zones that can spread the infection.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Initialize the queue with all the initially infected zones and count the total number of safe zones (1s). Perform BFS to spread the infection hour by hour, infecting adjacent safe zones until no more infections can occur. If all safe zones are infected, return the number of hours it took. If there are any remaining safe zones, return -1.

1) Define a helper function `next_moves` to return valid adjacent safe zones for infection.
2) Initialize a queue with all initially infected zones (`2`s).
3) Count the total number of safe zones (`1`s).
4) Perform BFS:
    a) For each infected zone in the queue, infect adjacent safe zones and add them to the queue.
    b) Decrease the count of safe zones each time a zone is infected.
    c) Increment the hour after each BFS level.
5) If there are no safe zones left, return the number of hours it took to infect the entire city.
6) If there are still safe zones remaining after BFS, return `-1`.

⚠️ Common Mistakes

  • Forgetting to decrement the safe zone count after each infection.
  • Not accounting for grids that have no safe zones at the start.
  • Failing to check whether any safe zones remain after BFS.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

# Helper function to find valid next moves (safe zones to infect)
def next_moves(position, grid):
    row, col = position
    rows, cols = len(grid), len(grid[0])
    
    # Directions for moving up, down, left, and right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # List to hold the valid next moves
    valid_moves = []
    
    # Check each direction
    for d_row, d_col in directions:
        new_row, new_col = row + d_row, col + d_col
        # Ensure the new position is within the grid bounds and is a safe zone (1)
        if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == 1:
            valid_moves.append((new_row, new_col))
    
    return valid_moves

# BFS function to simulate the spread of the infection
def time_to_infect(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    safe_zones = 0  # Count of human safe zones
    
    # Initialize the queue with all the initially infected zones
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                safe_zones += 1  # Count the total number of safe zones (humans)
    
    # If there are no safe zones, return 0
    if safe_zones == 0:
        return 0
    
    hours = 0
    
    # Perform BFS
    while queue:
        # Process all the infected zones at the current hour
        for _ in range(len(queue)):
            row, col = queue.popleft()
            # Get the valid next moves (adjacent safe zones to infect)
            for new_row, new_col in next_moves((row, col), grid):
                # Infect the safe zone
                grid[new_row][new_col] = 2
                queue.append((new_row, new_col))
                safe_zones -= 1  # Decrease the count of safe zones
        
        hours += 1  # Increase the hour after processing all current infections
    
    # If there are still safe zones left, return -1
    return hours - 1 if safe_zones == 0 else -1

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 = [ [2,1,1], [1,1,0], [0,1,1] ]
  • Expected Output: 4
  • Watchlist:
    • Ensure safe_zones is decremented correctly when infection spreads.
    • Check the number of iterations of the while loop (representing hours).
    • Verify that BFS is correctly processing each level of infection spread.

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 every cell is visited at most once during BFS.
  • Space Complexity: O(m * n) due to the queue storing all infected zones and the grid.