Nearest Zombie - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

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

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 are distances calculated?
    • The distance between two adjacent cells (horizontally/vertically) is 1.
  • Can we start BFS from multiple points?
    • Yes, we can start from all zombie cells (0s) and perform BFS to calculate the distance to the nearest zombie for all human cells (1s).
  • What should be the distance for zombie cells?
    • The distance for a zombie cell to itself is 0.
HAPPY CASE
Input: grid = [
    [0,0,0],
    [0,1,0],
    [0,0,0]
]
Output: [
    [0,0,0],
    [0,1,0],
    [0,0,0]
]
Explanation: The nearest zombie for the human at (1, 1) is at distance 1.

EDGE CASE
Input: grid = [
    [0,0,0],
    [0,1,0],
    [1,1,1]
]
Output: [
    [0,0,0],
    [0,1,0],
    [1,2,1]
]
Explanation: The humans at the bottom are at distances 1 and 2 from the nearest zombies.

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:

  • Breadth-First Search (BFS): BFS is the optimal choice for finding the shortest path in an unweighted grid. We can start BFS from all zombie cells simultaneously.
  • Multi-source BFS: Since zombies are the sources of infection, we can treat this as a multi-source BFS problem.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Start BFS from all zombie cells (0s) and calculate the distance for each human cell (1) to the nearest zombie. Initialize the distances for all zombie cells as 0 and propagate the distance as we traverse the grid.

1) Initialize a 2D array `distances` to store the distance of each cell to the nearest zombie.
2) Add all zombie cells to the BFS queue and mark their distances as `0`.
3) Perform BFS:
    a) For each cell, check its valid neighbors.
    b) If the neighbor is a human cell, update its distance and continue BFS.
4) Return the `distances` grid.

⚠️ Common Mistakes

  • Forgetting to mark cells as visited can lead to infinite loops.
  • Not handling edge cases where there are no zombies or no humans.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

# Helper function to find valid next moves
def next_moves(position, grid, visited):
    row, col = position
    rows, cols = len(grid), len(grid[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 and not visited[new_row][new_col]:
            valid_moves.append((new_row, new_col))
    
    return valid_moves

# BFS function to calculate the nearest zombie distances
def nearest_zombie(grid):
    m, n = len(grid), len(grid[0])
    
    # Initialize distances with -1, which will be updated during BFS
    distances = [[-1] * n for _ in range(m)]
    
    # Initialize the queue and visited set
    queue = deque()
    visited = [[False] * n for _ in range(m)]
    
    # Start BFS from all zombie cells (grid[row][col] == 0)
    for row in range(m):
        for col in range(n):
            if grid[row][col] == 0:  # Zombie
                queue.append((row, col))
                distances[row][col] = 0  # Distance to the nearest zombie is 0
                visited[row][col] = True
    
    # Perform BFS
    while queue:
        current_row, current_col = queue.popleft()
        
        # Get the valid next moves
        for next_row, next_col in next_moves((current_row, current_col), grid, visited):
            # Update the distance for the human cell (grid[row][col] == 1)
            distances[next_row][next_col] = distances[current_row][current_col] + 1
            visited[next_row][next_col] = True
            queue.append((next_row, next_col))
    
    return distances

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 = [ [0,0,0], [0,1,0], [0,0,0] ]
  • Expected Output: [ [0,0,0], [0,1,0], [0,0,0] ]
  • Watchlist:
    • Ensure BFS starts correctly from all zombie cells.
    • Verify that all human cells have the correct distances calculated.

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 processed once during BFS.
  • Space Complexity: O(m * n) due to the queue, visited array, and distance array.