Jobs

Interviews

Discussions

01 Matrix

Medium

01 Matrix

Medium

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 dimensions (m and n) of the matrix? Are there any constraints on the maximum or minimum values of m and n?
Can the matrix be empty (m=0 or n=0)? If so, what should the output be?
Will the input matrix always contain at least one 0?
Are all values guaranteed to be either 0 or 1? Or could there be other integer values?
Is there any specific behavior expected if there are multiple 'nearest 0' cells at the same distance for a given '1' cell?

Brute Force Solution

Approach

Imagine you're looking at a grid of cells, some marked 'zero' and others marked 'one'. The brute force method finds, for each 'one' cell, how far away the nearest 'zero' cell is by checking every possibility. It explores outwards from each 'one' cell, step by step, until it finds a 'zero'.

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

For every cell that has a 'one', we will start a search.
From that 'one' cell, check all the cells right next to it.
If any of those neighbors are 'zero', then we know the distance is one, and we're done with that 'one' cell.
If none of the neighbors are 'zero', check all the cells that are two steps away.
Keep expanding the search to cells that are three steps away, four steps away, and so on.
As soon as we find a 'zero', we record the number of steps it took to get there as the distance for that original 'one' cell.
Repeat this process for every 'one' cell in the grid.

Code Implementation

def zero_one_matrix_brute_force(matrix):
    number_rows = len(matrix)
    number_columns = len(matrix[0])
    result_matrix = [[0] * number_columns for _ in range(number_rows)]

    for row in range(number_rows):
        for column in range(number_columns):
            if matrix[row][column] == 1:
                distance = 0
                found_zero = False

                while not found_zero:
                    distance += 1
                    # Explore outwards, increasing the search radius
                    for row_offset in range(-distance, distance + 1):
                        column_offset = distance - abs(row_offset)

                        if 0 <= row + row_offset < number_rows and 0 <= column + column_offset < number_columns:
                            if matrix[row + row_offset][column + column_offset] == 0:
                                result_matrix[row][column] = distance
                                found_zero = True
                                break

                        column_offset = -column_offset

                        if 0 <= row + row_offset < number_rows and 0 <= column + column_offset < number_columns and column_offset != (distance - abs(row_offset)) * -1:
                            if matrix[row + row_offset][column + column_offset] == 0:
                                result_matrix[row][column] = distance
                                found_zero = True
                                break

                    if found_zero:
                        break

    return result_matrix

Big(O) Analysis

Time Complexity

O(m*n*m*n) – For an m x n matrix, the brute force approach iterates through each cell (m*n). For each 'one' cell, in the worst case, it might have to explore all other cells in the matrix to find the nearest 'zero'. This exploration, in the worst case, expands outward layer by layer, potentially visiting each of the m*n cells. Therefore, the overall time complexity is O(m*n*m*n) because, for each of the m*n cells, we potentially perform a search that takes O(m*n) time.

Space Complexity

O(1) – The described brute force approach calculates the distance for each 'one' cell individually without storing intermediate results across different cells. While the algorithm iterates through neighbors to find the nearest 'zero', the number of neighbor cells checked in each step is limited by the dimensions of the grid and does not scale with the total number of cells N. Therefore, the auxiliary space used for managing indices and distance counters is constant and independent of the input size N, resulting in O(1) space complexity.

Optimal Solution

Approach

The best way to solve this is to think about building outwards from the zeroes. Imagine the zeroes are like sources of water, and the numbers around them get 'wet' based on how far away they are from the water. We can efficiently find the distance to the nearest zero for every number in the grid.

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

First, pretend all the numbers are infinitely far away from any zero. This lets us update them as we find closer zeroes.
Next, go through the grid from top to bottom and left to right. For each number, check if its neighbors above and to the left have shorter distances to a zero. If they do, update the number's distance.
Then, go through the grid again, but this time from bottom to top and right to left. Check if the neighbors below and to the right have shorter distances. Update the number's distance again if needed.
By doing these two passes, we've considered all possible paths from each number to the nearest zero, and found the shortest one.

Code Implementation

def zero_one_matrix(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    maximum_distance = rows + cols

    # Initialize all non-zero elements to infinity
    for row_index in range(rows):
        for col_index in range(cols):
            if matrix[row_index][col_index] != 0:
                matrix[row_index][col_index] = maximum_distance

    # Top to bottom, left to right
    for row_index in range(rows):
        for col_index in range(cols):
            if matrix[row_index][col_index] != 0:

                # Check top neighbor if within bounds
                if row_index > 0:
                    matrix[row_index][col_index] = min(matrix[row_index][col_index], matrix[row_index-1][col_index] + 1)

                # Check left neighbor if within bounds
                if col_index > 0:
                    matrix[row_index][col_index] = min(matrix[row_index][col_index], matrix[row_index][col_index-1] + 1)

    # Bottom to top, right to left
    for row_index in range(rows-1, -1, -1):
        for col_index in range(cols-1, -1, -1):
            if matrix[row_index][col_index] != 0:
                # Check bottom neighbor if within bounds
                if row_index < rows - 1:
                    matrix[row_index][col_index] = min(matrix[row_index][col_index], matrix[row_index+1][col_index] + 1)

                # Check right neighbor if within bounds
                if col_index < cols - 1:
                    matrix[row_index][col_index] = min(matrix[row_index][col_index], matrix[row_index][col_index+1] + 1)

    return matrix

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through the entire matrix twice. The first pass iterates from top-left to bottom-right, and the second pass iterates from bottom-right to top-left. Each pass visits every cell in the m x n matrix once. Therefore, the time complexity is proportional to the number of cells in the matrix, which is m*n. Thus the overall time complexity is O(m*n).

Space Complexity

O(1) – The provided algorithm operates in-place, modifying the input matrix directly to store the distances. It doesn't create any significant auxiliary data structures like arrays, lists, or hash maps that scale with the input size (N, where N is the number of cells in the matrix). The only extra memory used consists of a few constant variables for iteration and comparison during the passes through the grid. Therefore, the auxiliary space complexity is constant, independent of the input matrix size.

Edge Cases

Case	How to Handle
Null or empty input matrix	Return null or an empty matrix to indicate invalid input.
Matrix with only one cell	Return a matrix with a single cell containing 0 if the cell is 0, or infinity (represented by a large number) if the cell is 1.
Matrix with all 0s	The resulting matrix will be all 0s, handled correctly by BFS since initial queue will contain all cells.
Matrix with all 1s	The resulting matrix will contain the distance to the nearest boundary, which can be handled by initializing the result with infinity (a large number) and updating during BFS.
Very large matrix (memory constraints)	BFS approach works as it processes nodes level by level; however, large queue size might exhaust memory, so consider memory optimization techniques if available.
Integer overflow when calculating distances in large matrices	Use a data type with sufficient range (e.g., long) to store the distances, or implement checks to prevent overflow.
Matrix with a single 0 surrounded by 1s	The BFS algorithm will correctly propagate the distance from the single 0 to its surrounding 1s.
Disconnected regions of 0s	The BFS algorithm will correctly calculate distances from each region of 0s independently.

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 dimensions (m and n) of the matrix? Are there any constraints on the maximum or minimum values of m and n?
Can the matrix be empty (m=0 or n=0)? If so, what should the output be?
Will the input matrix always contain at least one 0?
Are all values guaranteed to be either 0 or 1? Or could there be other integer values?
Is there any specific behavior expected if there are multiple 'nearest 0' cells at the same distance for a given '1' cell?

Brute Force Solution

Approach

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

For every cell that has a 'one', we will start a search.
From that 'one' cell, check all the cells right next to it.
If any of those neighbors are 'zero', then we know the distance is one, and we're done with that 'one' cell.
If none of the neighbors are 'zero', check all the cells that are two steps away.
Keep expanding the search to cells that are three steps away, four steps away, and so on.
As soon as we find a 'zero', we record the number of steps it took to get there as the distance for that original 'one' cell.
Repeat this process for every 'one' cell in the grid.

Code Implementation

def zero_one_matrix_brute_force(matrix):
    number_rows = len(matrix)
    number_columns = len(matrix[0])
    result_matrix = [[0] * number_columns for _ in range(number_rows)]

    for row in range(number_rows):
        for column in range(number_columns):
            if matrix[row][column] == 1:
                distance = 0
                found_zero = False

                while not found_zero:
                    distance += 1
                    # Explore outwards, increasing the search radius
                    for row_offset in range(-distance, distance + 1):
                        column_offset = distance - abs(row_offset)

                        if 0 <= row + row_offset < number_rows and 0 <= column + column_offset < number_columns:
                            if matrix[row + row_offset][column + column_offset] == 0:
                                result_matrix[row][column] = distance
                                found_zero = True
                                break

                        column_offset = -column_offset

                        if 0 <= row + row_offset < number_rows and 0 <= column + column_offset < number_columns and column_offset != (distance - abs(row_offset)) * -1:
                            if matrix[row + row_offset][column + column_offset] == 0:
                                result_matrix[row][column] = distance
                                found_zero = True
                                break

                    if found_zero:
                        break

    return result_matrix

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, pretend all the numbers are infinitely far away from any zero. This lets us update them as we find closer zeroes.
Next, go through the grid from top to bottom and left to right. For each number, check if its neighbors above and to the left have shorter distances to a zero. If they do, update the number's distance.
Then, go through the grid again, but this time from bottom to top and right to left. Check if the neighbors below and to the right have shorter distances. Update the number's distance again if needed.
By doing these two passes, we've considered all possible paths from each number to the nearest zero, and found the shortest one.

Code Implementation

def zero_one_matrix(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    maximum_distance = rows + cols

    # Initialize all non-zero elements to infinity
    for row_index in range(rows):
        for col_index in range(cols):
            if matrix[row_index][col_index] != 0:
                matrix[row_index][col_index] = maximum_distance

    # Top to bottom, left to right
    for row_index in range(rows):
        for col_index in range(cols):
            if matrix[row_index][col_index] != 0:

                # Check top neighbor if within bounds
                if row_index > 0:
                    matrix[row_index][col_index] = min(matrix[row_index][col_index], matrix[row_index-1][col_index] + 1)

                # Check left neighbor if within bounds
                if col_index > 0:
                    matrix[row_index][col_index] = min(matrix[row_index][col_index], matrix[row_index][col_index-1] + 1)

    # Bottom to top, right to left
    for row_index in range(rows-1, -1, -1):
        for col_index in range(cols-1, -1, -1):
            if matrix[row_index][col_index] != 0:
                # Check bottom neighbor if within bounds
                if row_index < rows - 1:
                    matrix[row_index][col_index] = min(matrix[row_index][col_index], matrix[row_index+1][col_index] + 1)

                # Check right neighbor if within bounds
                if col_index < cols - 1:
                    matrix[row_index][col_index] = min(matrix[row_index][col_index], matrix[row_index][col_index+1] + 1)

    return matrix

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input matrix	Return null or an empty matrix to indicate invalid input.
Matrix with only one cell	Return a matrix with a single cell containing 0 if the cell is 0, or infinity (represented by a large number) if the cell is 1.
Matrix with all 0s	The resulting matrix will be all 0s, handled correctly by BFS since initial queue will contain all cells.
Matrix with all 1s	The resulting matrix will contain the distance to the nearest boundary, which can be handled by initializing the result with infinity (a large number) and updating during BFS.
Very large matrix (memory constraints)	BFS approach works as it processes nodes level by level; however, large queue size might exhaust memory, so consider memory optimization techniques if available.
Integer overflow when calculating distances in large matrices	Use a data type with sufficient range (e.g., long) to store the distances, or implement checks to prevent overflow.
Matrix with a single 0 surrounded by 1s	The BFS algorithm will correctly propagate the distance from the single 0 to its surrounding 1s.
Disconnected regions of 0s	The BFS algorithm will correctly calculate distances from each region of 0s independently.