Jobs

Interviews

Discussions

Walls and Gates

Medium

Amazon

2 views

Topics:

Graphs

You are given an m x n grid rooms initialized with these three possible values.

INF which represents an empty room (represented as 2147483647)
-1 represents a wall
0 represents a gate.

You are to fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, that room should remain INF.

For example, given the following input:

[   [INF, -1,  0,  INF],
    [INF, INF, INF, -1],
    [INF, -1,  INF, -1],
    [0,  -1,  INF, INF]
]

Your function should modify the input rooms array in-place to look like this:

[   [3, -1, 0, 1],
    [2, 2, 1, -1],
    [1, -1, 2, -1],
    [0, -1, 3, 4]
]

Explain your approach, analyze its time and space complexity, and handle any potential edge cases. Provide the code for your solution. The goal is to find the most efficient way to solve this problem.

Walls and Gates

Medium

Amazon

2 views

Topics:

Graphs

You are given an m x n grid rooms initialized with these three possible values.

INF which represents an empty room (represented as 2147483647)
-1 represents a wall
0 represents a gate.

You are to fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, that room should remain INF.

For example, given the following input:

[   [INF, -1,  0,  INF],
    [INF, INF, INF, -1],
    [INF, -1,  INF, -1],
    [0,  -1,  INF, INF]
]

Your function should modify the input rooms array in-place to look like this:

[   [3, -1, 0, 1],
    [2, 2, 1, -1],
    [1, -1, 2, -1],
    [0, -1, 3, 4]
]

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values in the matrix, and what do each of those values represent specifically (e.g., -1, 0, INF)?
Can the matrix be empty or contain null values?
Is it possible for the matrix to contain no gates (i.e., all walls or rooms)? What should the output be in this case?
The 'INF' value represents infinity, but what is the actual integer value used to represent infinity in the matrix? Will it be a very large number, or some other specific value?
Should I modify the input matrix in place, or should I return a new matrix with the distances?

Brute Force Solution

Approach

Imagine you're exploring a building with rooms and want to find the shortest path from each room to the nearest exit. The brute force way involves walking from each room to every other room until you find an exit. You then repeat this process for all of the other rooms.

Here's how the algorithm would work step-by-step:

Start at one room.
From that room, try going to every other room in the building.
If you reach an exit, record the number of steps you took to get there.
If you don't reach an exit from a specific path, just try another path from your starting room until you have exhausted all possibilities.
From your starting room, consider every possible route to all other rooms, and see if any of those routes leads you to a room that is an exit.
Keep track of the shortest route you found from that starting room to any exit.
Repeat this entire process, starting from each different room in the building.
Once you have calculated the shortest path from every room to an exit, you are done.

Code Implementation

def walls_and_gates_brute_force(rooms):
    rows = len(rooms)
    cols = len(rooms[0]) if rows > 0 else 0

    def find_shortest_path(start_row, start_col):
        shortest_distance = float('inf')

        def explore(current_row, current_col, distance, visited):
            nonlocal shortest_distance

            # Prevent infinite loops by marking as visited
            if (current_row, current_col) in visited:
                return

            if not (0 <= current_row < rows and 0 <= current_col < cols):
                return

            if rooms[current_row][current_col] == -1:
                return

            # We found a gate
            if rooms[current_row][current_col] == 0:
                shortest_distance = min(shortest_distance, distance)
                return

            visited.add((current_row, current_col))

            explore(current_row + 1, current_col, distance + 1, visited.copy())

            explore(current_row - 1, current_col, distance + 1, visited.copy())

            explore(current_row, current_col + 1, distance + 1, visited.copy())

            explore(current_row, current_col - 1, distance + 1, visited.copy())

        explore(start_row, start_col, 0, set())
        return shortest_distance

    for row_index in range(rows):
        for col_index in range(cols):
            # Only process rooms that are not walls or gates
            if rooms[row_index][col_index] == 2147483647:
                rooms[row_index][col_index] = find_shortest_path(row_index, col_index)

Big(O) Analysis

Time Complexity

O(n^3) – The given brute force approach iterates through each room in the building, which can be considered as n rooms. From each room, it potentially explores every other room, leading to another loop of n. In the worst case, to find the shortest path from a starting room to an exit, it may have to explore all possible paths, and the length of such paths can also be proportional to n. Therefore, the time complexity is approximately n * n * n, which simplifies to O(n^3).

Space Complexity

O(1) – The plain English explanation suggests an iterative approach that focuses on exploring paths and tracking the shortest distance. No explicit auxiliary data structures like queues, stacks, or large temporary arrays are mentioned. The steps indicate comparing distances and updating a shortest distance, implying constant space usage regardless of the building's layout, which is implicitly represented as the input (size N). Therefore, the space complexity is O(1) as it uses a constant amount of extra memory.

Optimal Solution

Approach

The problem is to fill in the empty rooms with the shortest distance to a gate. We can efficiently do this by starting at the gates and spreading outwards, layer by layer, updating each empty room's distance as we go. This ensures we find the shortest paths without re-calculating.

Here's how the algorithm would work step-by-step:

Find all the gates in the grid. These are our starting points.
Imagine sending out waves from each gate simultaneously. Each wave increases the distance from the gate by one.
For each wave, look at all the neighbors (up, down, left, right) of the cells that are currently at the edge of our wave.
If a neighbor is an empty room and hasn't been visited yet, update its distance to be the current wave's distance and add it to the next wave.
Continue expanding the waves until we've explored all reachable empty rooms. Any empty rooms that remain with their initial infinite distance are unreachable from any gate.

Code Implementation

def walls_and_gates(rooms):
    if not rooms:
        return

    rows_count = len(rooms)
    columns_count = len(rooms[0])
    queue = []

    # Find all gates and add them to the queue for BFS
    for row_index in range(rows_count):
        for column_index in range(columns_count):
            if rooms[row_index][column_index] == 0:
                queue.append((row_index, column_index))

    def add_room_to_queue(row_index, column_index, distance):
        if 0 <= row_index < rows_count and 0 <= column_index < columns_count and \
           rooms[row_index][column_index] == 2147483647:
            rooms[row_index][column_index] = distance
            queue.append((row_index, column_index))

    # BFS to find the shortest distance to each room
    distance = 1

    while queue:
        next_queue = []
        for _ in range(len(queue)):
            row_index, column_index = queue.pop(0)

            # Check the neighbors of the current room
            add_room_to_queue(row_index + 1, column_index, distance)
            add_room_to_queue(row_index - 1, column_index, distance)
            add_room_to_queue(row_index, column_index + 1, distance)
            add_room_to_queue(row_index, column_index - 1, distance)

        distance += 1

Big(O) Analysis

Time Complexity

O(m*n) – Let m be the number of rows and n be the number of columns in the grid. The algorithm essentially visits each reachable room from a gate at most once. In the worst-case scenario, the algorithm explores all the cells in the grid. Finding all the gates initially takes O(m*n). The breadth-first search (BFS) spreads outwards from each gate. Each cell is added to the queue at most once. Therefore, the overall time complexity is proportional to the number of cells in the grid. Thus, the total operations approximate m * n, simplifying to O(m*n).

Space Complexity

O(W*H) – The primary auxiliary space usage comes from the queue used to perform the breadth-first search, where W is the width and H is the height of the grid. In the worst-case scenario, the queue could contain all empty rooms in the grid, requiring space proportional to the number of cells in the grid. Thus, the space complexity is O(W*H), where W is the width and H is the height of the grid. Since the input grid size is related to N, we can simplify the space complexity to O(N), where N represents the total number of cells in the grid.

Edge Cases

Case	How to Handle
Null or empty rooms array	Return immediately without processing, as there are no rooms to update.
Rooms array with zero rows or zero columns	Return immediately, handling it as an invalid input scenario.
All rooms are walls (-1)	The algorithm should terminate without modifying the grid, as there are no gates to start from.
All rooms are gates (0)	The algorithm will iterate through the grid and all adjacent rooms will be updated to 1.
All rooms are empty (INF = 2147483647)	The algorithm will correctly update all rooms with the distance to the nearest gate.
Grid with only one cell which is a gate	The cell will remain 0 and the algorithm terminates.
Grid with only one cell which is a wall	The cell will remain -1 and the algorithm terminates.
Integer overflow when calculating distances from gates	The problem statement specifies INF as 2147483647, and using BFS ensures distances won't exceed this value since we are increasing by 1 at each step.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values in the matrix, and what do each of those values represent specifically (e.g., -1, 0, INF)?
Can the matrix be empty or contain null values?
Is it possible for the matrix to contain no gates (i.e., all walls or rooms)? What should the output be in this case?
The 'INF' value represents infinity, but what is the actual integer value used to represent infinity in the matrix? Will it be a very large number, or some other specific value?
Should I modify the input matrix in place, or should I return a new matrix with the distances?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at one room.
From that room, try going to every other room in the building.
If you reach an exit, record the number of steps you took to get there.
If you don't reach an exit from a specific path, just try another path from your starting room until you have exhausted all possibilities.
From your starting room, consider every possible route to all other rooms, and see if any of those routes leads you to a room that is an exit.
Keep track of the shortest route you found from that starting room to any exit.
Repeat this entire process, starting from each different room in the building.
Once you have calculated the shortest path from every room to an exit, you are done.

Code Implementation

def walls_and_gates_brute_force(rooms):
    rows = len(rooms)
    cols = len(rooms[0]) if rows > 0 else 0

    def find_shortest_path(start_row, start_col):
        shortest_distance = float('inf')

        def explore(current_row, current_col, distance, visited):
            nonlocal shortest_distance

            # Prevent infinite loops by marking as visited
            if (current_row, current_col) in visited:
                return

            if not (0 <= current_row < rows and 0 <= current_col < cols):
                return

            if rooms[current_row][current_col] == -1:
                return

            # We found a gate
            if rooms[current_row][current_col] == 0:
                shortest_distance = min(shortest_distance, distance)
                return

            visited.add((current_row, current_col))

            explore(current_row + 1, current_col, distance + 1, visited.copy())

            explore(current_row - 1, current_col, distance + 1, visited.copy())

            explore(current_row, current_col + 1, distance + 1, visited.copy())

            explore(current_row, current_col - 1, distance + 1, visited.copy())

        explore(start_row, start_col, 0, set())
        return shortest_distance

    for row_index in range(rows):
        for col_index in range(cols):
            # Only process rooms that are not walls or gates
            if rooms[row_index][col_index] == 2147483647:
                rooms[row_index][col_index] = find_shortest_path(row_index, col_index)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Find all the gates in the grid. These are our starting points.
Imagine sending out waves from each gate simultaneously. Each wave increases the distance from the gate by one.
For each wave, look at all the neighbors (up, down, left, right) of the cells that are currently at the edge of our wave.
If a neighbor is an empty room and hasn't been visited yet, update its distance to be the current wave's distance and add it to the next wave.
Continue expanding the waves until we've explored all reachable empty rooms. Any empty rooms that remain with their initial infinite distance are unreachable from any gate.

Code Implementation

def walls_and_gates(rooms):
    if not rooms:
        return

    rows_count = len(rooms)
    columns_count = len(rooms[0])
    queue = []

    # Find all gates and add them to the queue for BFS
    for row_index in range(rows_count):
        for column_index in range(columns_count):
            if rooms[row_index][column_index] == 0:
                queue.append((row_index, column_index))

    def add_room_to_queue(row_index, column_index, distance):
        if 0 <= row_index < rows_count and 0 <= column_index < columns_count and \
           rooms[row_index][column_index] == 2147483647:
            rooms[row_index][column_index] = distance
            queue.append((row_index, column_index))

    # BFS to find the shortest distance to each room
    distance = 1

    while queue:
        next_queue = []
        for _ in range(len(queue)):
            row_index, column_index = queue.pop(0)

            # Check the neighbors of the current room
            add_room_to_queue(row_index + 1, column_index, distance)
            add_room_to_queue(row_index - 1, column_index, distance)
            add_room_to_queue(row_index, column_index + 1, distance)
            add_room_to_queue(row_index, column_index - 1, distance)

        distance += 1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty rooms array	Return immediately without processing, as there are no rooms to update.
Rooms array with zero rows or zero columns	Return immediately, handling it as an invalid input scenario.
All rooms are walls (-1)	The algorithm should terminate without modifying the grid, as there are no gates to start from.
All rooms are gates (0)	The algorithm will iterate through the grid and all adjacent rooms will be updated to 1.
All rooms are empty (INF = 2147483647)	The algorithm will correctly update all rooms with the distance to the nearest gate.
Grid with only one cell which is a gate	The cell will remain 0 and the algorithm terminates.
Grid with only one cell which is a wall	The cell will remain -1 and the algorithm terminates.
Integer overflow when calculating distances from gates	The problem statement specifies INF as 2147483647, and using BFS ensures distances won't exceed this value since we are increasing by 1 at each step.