Jobs

Interviews

Discussions

Set Matrix Zeroes

Medium

Set Matrix Zeroes

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 constraints on the dimensions of the matrix, m and n? What is the maximum size I should consider?
What is the range of integer values within the matrix? Should I expect negative numbers, or any values that could cause integer overflow during calculations?
If the input matrix is null or empty (m=0 or n=0), what should my code do?
Is the input matrix guaranteed to be rectangular, or can the rows have varying lengths?
Are we optimizing for space complexity in addition to time complexity? If so, what space complexity is acceptable?

Brute Force Solution

Approach

The brute force way to solve this is to check every spot in the matrix. If we find a zero, we need to remember its location so we can change its row and column later. We will then go back through and change the rows and columns containing the zeros we remembered.

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

Go through each position in the matrix, one by one.
If you find a zero, make a note of that position.
After checking every position, go back to the first zero you noted.
Change all the numbers in the same row and column as that zero to zeros.
Do the same for every other zero you noted.

Code Implementation

def set_matrix_zeroes_brute_force(matrix):
    rows_with_zero = len(matrix)
    cols_with_zero = len(matrix[0])

    zero_positions = []

    for row_index in range(rows_with_zero):
        for col_index in range(cols_with_zero):
            if matrix[row_index][col_index] == 0:
                zero_positions.append((row_index, col_index))

    # Iterate through the stored zero positions.
    for zero_row, zero_col in zero_positions:

        # Zero out the entire row
        for col_index in range(cols_with_zero):
            matrix[zero_row][col_index] = 0

        # Zero out the entire column
        for row_index in range(rows_with_zero):
            matrix[row_index][zero_col] = 0

    return matrix

Big(O) Analysis

Time Complexity

O(m*n*(m+n)) – The algorithm iterates through the entire matrix of m rows and n columns to identify zero elements, which takes O(m*n) time. For each identified zero, it then iterates through its corresponding row (n elements) and column (m elements) to set them to zero. In the worst case, we might find a zero at every location in the matrix, and for each of those zero locations, we would traverse its row and column. Therefore, the total time complexity becomes O(m*n) for identifying zeros plus O(m*n * (m+n)) for zeroing the rows and columns of each identified zero location. Simplifying gives O(m*n*(m+n)).

Space Complexity

O(M*N) – The described brute force approach requires storing the locations of all the zeros found in the matrix. In the worst-case scenario, the entire matrix consists of zeros. Therefore, we need to store M*N positions where M is the number of rows and N is the number of columns. This means that the space used grows linearly with the size of the input matrix. Hence, the auxiliary space complexity is O(M*N).

Optimal Solution

Approach

The problem requires us to modify a matrix so that if a cell is zero, its entire row and column become zero. The optimal approach avoids using extra space by cleverly using the first row and column of the matrix itself to record which rows and columns need to be zeroed out.

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

First, check if the first row or the first column contains any zeros. We will need this information later to decide whether the entire first row or column should be zeroed out.
Next, go through the rest of the matrix. If you find a zero, mark the corresponding position in the first row and the corresponding position in the first column as zero. This tells us that the row and column associated with this zero need to be zeroed.
After scanning the entire matrix, go through the matrix again, but this time starting from the second row and second column. If you see a zero in the first row or first column for a particular cell, set that cell to zero.
Finally, use the information we saved from the very beginning about the first row and first column. If the first row originally contained a zero, make the entire first row zero. Do the same for the first column.
By using the first row and column as a temporary storage, we can modify the matrix in place, without needing any extra space.

Code Implementation

def set_matrix_zeroes(matrix):
    first_row_has_zero = False
    first_column_has_zero = False
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    for column_index in range(number_of_columns):
        if matrix[0][column_index] == 0:
            first_row_has_zero = True
            break

    for row_index in range(number_of_rows):
        if matrix[row_index][0] == 0:
            first_column_has_zero = True
            break

    # Mark rows and columns that need to be zeroed
    # using the first row and first column.
    for row_index in range(1, number_of_rows):
        for column_index in range(1, number_of_columns):
            if matrix[row_index][column_index] == 0:
                matrix[0][column_index] = 0
                matrix[row_index][0] = 0

    # Use the marks in the first row and column
    # to set the inner matrix elements to zero.
    for row_index in range(1, number_of_rows):
        for column_index in range(1, number_of_columns):
            if matrix[0][column_index] == 0 or matrix[row_index][0] == 0:
                matrix[row_index][column_index] = 0

    # Zero out the first row if needed.
    if first_row_has_zero:

        for column_index in range(number_of_columns):
            matrix[0][column_index] = 0

    # Zero out the first column if needed.
    if first_column_has_zero:

        for row_index in range(number_of_rows):
            matrix[row_index][0] = 0

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through the entire m x n matrix multiple times. Initially, it checks the first row and column, which takes O(m) and O(n) time, respectively. Then, it iterates through the entire matrix once to mark the first row and column based on zero locations, which takes O(m*n) time. Subsequently, it iterates again from the second row and column to set elements to zero based on the marked first row and column, also taking O(m*n) time. Finally, it potentially zeroes out the first row and column which takes O(m) and O(n) time, respectively. Since O(m*n) dominates, the overall time complexity is O(m*n).

Space Complexity

O(1) – The algorithm uses only two boolean variables to record if the first row and first column initially contain zeros. No other data structures that scale with the input matrix size are used. Therefore, the auxiliary space required remains constant irrespective of the matrix dimensions (number of rows and columns), resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty matrix (matrix == null or matrix.length == 0 or matrix[0].length == 0)	Return immediately as there's nothing to process; no modification needed.
Matrix with one row or one column	The in-place modification logic still works correctly for single rows or columns because we iterate through all cells.
Matrix with all zeros	All rows and columns will be zeroed out correctly by identifying the initial zero cells.
Matrix with no zeros	The matrix remains unchanged as no zero elements are found, thus no rows or columns are modified.
Large matrix (m and n are large, approaching memory limits)	The space-optimized solution using the first row and column as flags will scale better than using extra memory for row/col sets but still needs to be considered for large datasets; potential for memory issues remains.
Matrix containing very large or very small integer values (close to Integer.MAX_VALUE or Integer.MIN_VALUE)	Integer overflow is not a relevant concern for this algorithm as it only deals with equality (checking for zeros) and not arithmetic operations on the values themselves.
First cell in the matrix is zero	Special attention is required because the first row and column are used as flags, so we need to use additional variables to track their initial zero status before zeroing out.
Sparse matrix (few non-zero elements)	The algorithm will still perform correctly; it iterates over all elements regardless of their values and sets row/col flags appropriately for zeros.

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 constraints on the dimensions of the matrix, m and n? What is the maximum size I should consider?
What is the range of integer values within the matrix? Should I expect negative numbers, or any values that could cause integer overflow during calculations?
If the input matrix is null or empty (m=0 or n=0), what should my code do?
Is the input matrix guaranteed to be rectangular, or can the rows have varying lengths?
Are we optimizing for space complexity in addition to time complexity? If so, what space complexity is acceptable?

Brute Force Solution

Approach

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

Go through each position in the matrix, one by one.
If you find a zero, make a note of that position.
After checking every position, go back to the first zero you noted.
Change all the numbers in the same row and column as that zero to zeros.
Do the same for every other zero you noted.

Code Implementation

def set_matrix_zeroes_brute_force(matrix):
    rows_with_zero = len(matrix)
    cols_with_zero = len(matrix[0])

    zero_positions = []

    for row_index in range(rows_with_zero):
        for col_index in range(cols_with_zero):
            if matrix[row_index][col_index] == 0:
                zero_positions.append((row_index, col_index))

    # Iterate through the stored zero positions.
    for zero_row, zero_col in zero_positions:

        # Zero out the entire row
        for col_index in range(cols_with_zero):
            matrix[zero_row][col_index] = 0

        # Zero out the entire column
        for row_index in range(rows_with_zero):
            matrix[row_index][zero_col] = 0

    return matrix

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, check if the first row or the first column contains any zeros. We will need this information later to decide whether the entire first row or column should be zeroed out.
Next, go through the rest of the matrix. If you find a zero, mark the corresponding position in the first row and the corresponding position in the first column as zero. This tells us that the row and column associated with this zero need to be zeroed.
After scanning the entire matrix, go through the matrix again, but this time starting from the second row and second column. If you see a zero in the first row or first column for a particular cell, set that cell to zero.
Finally, use the information we saved from the very beginning about the first row and first column. If the first row originally contained a zero, make the entire first row zero. Do the same for the first column.
By using the first row and column as a temporary storage, we can modify the matrix in place, without needing any extra space.

Code Implementation

def set_matrix_zeroes(matrix):
    first_row_has_zero = False
    first_column_has_zero = False
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    for column_index in range(number_of_columns):
        if matrix[0][column_index] == 0:
            first_row_has_zero = True
            break

    for row_index in range(number_of_rows):
        if matrix[row_index][0] == 0:
            first_column_has_zero = True
            break

    # Mark rows and columns that need to be zeroed
    # using the first row and first column.
    for row_index in range(1, number_of_rows):
        for column_index in range(1, number_of_columns):
            if matrix[row_index][column_index] == 0:
                matrix[0][column_index] = 0
                matrix[row_index][0] = 0

    # Use the marks in the first row and column
    # to set the inner matrix elements to zero.
    for row_index in range(1, number_of_rows):
        for column_index in range(1, number_of_columns):
            if matrix[0][column_index] == 0 or matrix[row_index][0] == 0:
                matrix[row_index][column_index] = 0

    # Zero out the first row if needed.
    if first_row_has_zero:

        for column_index in range(number_of_columns):
            matrix[0][column_index] = 0

    # Zero out the first column if needed.
    if first_column_has_zero:

        for row_index in range(number_of_rows):
            matrix[row_index][0] = 0

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix (matrix == null or matrix.length == 0 or matrix[0].length == 0)	Return immediately as there's nothing to process; no modification needed.
Matrix with one row or one column	The in-place modification logic still works correctly for single rows or columns because we iterate through all cells.
Matrix with all zeros	All rows and columns will be zeroed out correctly by identifying the initial zero cells.
Matrix with no zeros	The matrix remains unchanged as no zero elements are found, thus no rows or columns are modified.
Large matrix (m and n are large, approaching memory limits)	The space-optimized solution using the first row and column as flags will scale better than using extra memory for row/col sets but still needs to be considered for large datasets; potential for memory issues remains.
Matrix containing very large or very small integer values (close to Integer.MAX_VALUE or Integer.MIN_VALUE)	Integer overflow is not a relevant concern for this algorithm as it only deals with equality (checking for zeros) and not arithmetic operations on the values themselves.
First cell in the matrix is zero	Special attention is required because the first row and column are used as flags, so we need to use additional variables to track their initial zero status before zeroing out.
Sparse matrix (few non-zero elements)	The algorithm will still perform correctly; it iterates over all elements regardless of their values and sets row/col flags appropriately for zeros.