We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Walls and Gates

Number: 286

Difficulty: Medium

Paid? Yes

Companies: DoorDash, Meta, Google, Amazon, Bloomberg, Visa, TikTok, Uber, Microsoft, Snowflake, Salesforce

Problem Description

You are given an m x n grid called rooms. Each cell in the grid can have one of three values: -1 representing a wall or obstacle, 0 representing a gate, or INF (2147483647) representing an empty room. The goal is to fill each empty room with the number of steps to its nearest gate. If a gate cannot be reached from an empty room, its value remains INF.

Key Insights

  • Use a multi-source Breadth-First Search (BFS) starting from all the gates, as this allows spreading the shortest distance to each empty room.
  • Instead of starting from every empty room separately, starting from all gates simultaneously helps update all distances in one pass.
  • Only update a room if the new calculated distance is smaller than its current value to prevent unnecessary processing.
  • The problem is essentially a multi-source shortest path problem on a grid.

Space and Time Complexity

Time Complexity: O(m * n) where m and n are the dimensions of the grid, as each cell is processed at most once. Space Complexity: O(m * n) in the worst-case scenario used by the BFS queue.

Solution

The solution uses a multi-source BFS algorithm by initially enqueuing all the gate positions (cells with value 0). Then, for each cell obtained from the queue, check its four possible neighbors (up, down, left, right). If a neighbor is an empty room (INF), update its distance to be the current cell's distance plus one, and then enqueue the neighbor to process further. This ensures that each empty room gets the minimum distance from any gate.

Code Solutions

from collections import deque

def wallsAndGates(rooms):
    if not rooms or not rooms[0]:
        return
    
    rows, cols = len(rooms), len(rooms[0])
    # Directions: up, down, left, right.
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = deque()

    # Enqueue all gates (cells with 0).
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                queue.append((r, c))
    
    # Perform multi-source BFS.
    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            # Process neighbor if it is within bounds and is an empty room.
            if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == 2147483647:
                rooms[nr][nc] = rooms[r][c] + 1   # Update distance.
                queue.append((nr, nc))
← Back to All Questions