Walls and Gates - 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, Multi-source 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?
  • Can we travel through walls or obstacles?
    • No, walls (1s) are impassable.
  • What if the grid contains no gates?
    • The distances for all empty rooms should remain float('inf').
  • What is the meaning of ""distance""?
    • The number of steps required to reach the nearest gate by moving up, down, left, or right.
HAPPY CASE
Input: castle = [
    [float('inf'), -1, 0, float('inf')],
    [float('inf'), float('inf'), float('inf'), -1],
    [float('inf'), -1, float('inf'), -1],
    [0, -1, float('inf'), float('inf')]
]
Output: [
    [3, -1, 0, 1],
    [2, 2, 1, -1],
    [1, -1, 2, -1],
    [0, -1, 3, 4]
]
Explanation: The empty rooms are updated with their distances to the nearest gates.

EDGE CASE
Input: castle = [
    [1, -1],
    [-1, 1]
]
Output: [
    [1, -1],
    [-1, 1]
]
Explanation: There are no gates in the grid, so the grid remains unchanged.

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 ideal for finding the shortest distance to the nearest gate, as it explores all neighboring rooms level by level.
  • Multi-source BFS: In this case, multiple gates are the starting points, and BFS is performed from all gates simultaneously.
  • Queue: A queue is used to store the positions of the gates and process them in a BFS manner.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We can treat all gates (0s) as starting points and perform BFS from all gates simultaneously. For each empty room (float('inf')), its value will be updated to the shortest distance from any gate. Walls and obstacles (1s) are impassable and should be ignored.

1) Initialize a queue with all gates (cells with value `0`).
2) Perform BFS:
    a) For each gate, explore its neighboring rooms.
    b) If a neighboring room is empty (`float('inf')`), update its value to the current distance and add it to the queue.
3) Continue BFS until all reachable rooms have been updated.
4) Return the modified `castle` grid.

⚠️ Common Mistakes

  • Forgetting to check if the move is within grid bounds can lead to out-of-bounds errors.
  • Not handling the case where there are no gates can result in unnecessary BFS operations.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

# Adapted version of next_moves() to find valid neighboring rooms
def next_moves(castle, row, column):
    moves = [
        (row + 1, column),  # down
        (row - 1, column),  # up
        (row, column + 1),  # right
        (row, column - 1)   # left
    ]
    
    possible = []
    for r, c in moves:
        # Check if the move is within bounds and is an empty room (float('inf'))
        if (0 <= r < len(castle)
            and 0 <= c < len(castle[0])
            and castle[r][c] == float('inf')):
            possible.append((r, c))
    
    return possible

def walls_and_gates(castle):
    if not castle or not castle[0]:
        return
    
    # Initialize BFS queue and enqueue all gates (positions with value 0)
    queue = deque([(r, c) for r in range(len(castle)) for c in range(len(castle[0])) if castle[r][c] == 0])
    
    while queue:
        row, col = queue.popleft()
        
        # Get all valid neighboring rooms (infinity values) to move into
        for neighbor_row, neighbor_col in next_moves(castle, row, col):
            # Update the neighboring room's distance and add it to the queue
            castle[neighbor_row][neighbor_col] = castle[row][col] + 1
            queue.append((neighbor_row, neighbor_col))

    return castle

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: castle = [ [float('inf'), -1, 0, float('inf')], [float('inf'), float('inf'), float('inf'), -1], [float('inf'), -1, float('inf'), -1], [0, -1, float('inf'), float('inf')] ]
  • Expected Output: [ [3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4] ]
  • Watchlist:
    • Ensure that all gates are processed correctly in the BFS.
    • Verify that only empty rooms (float('inf')) are updated with distances.

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 processed once during BFS.
  • Space Complexity: O(m * n) due to the queue storing positions of rooms to be processed.