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

Set Matrix Zeroes

Difficulty: Medium

Problem Description

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. You must do it in place.

Key Insights

  • We need to modify the matrix in place without using additional space for another matrix.
  • We can use the first row and the first column of the matrix itself to keep track of which rows and columns need to be zeroed.
  • The algorithm requires two passes over the matrix: one to mark the zero rows and columns, and a second to set the appropriate elements to zero.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(1) (constant space for the in-place modification)

Solution

To solve the problem, we will utilize the first row and the first column of the matrix to track which rows and columns need to be set to zero. The steps are as follows:

  1. Iterate through the matrix to determine which rows and columns should be zeroed. We will use the first row and first column as markers.
  2. Use a flag to check if the first row and first column themselves need to be zeroed.
  3. Iterate through the matrix again (excluding the first row and column) to set the appropriate elements to zero based on the markers.
  4. Finally, zero out the first row and first column if necessary.

This approach ensures that we only use O(1) extra space while achieving the required modifications in the matrix.

Code Solutions

def setZeroes(matrix):
    if not matrix:
        return
    
    rows, cols = len(matrix), len(matrix[0])
    row_zero = False
    col_zero = False
    
    # Determine if the first row and first column should be zeroed
    for i in range(rows):
        if matrix[i][0] == 0:
            col_zero = True
    for j in range(cols):
        if matrix[0][j] == 0:
            row_zero = True
    
    # Use the first row and column as markers
    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    
    # Set matrix cells to zero based on markers
    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    
    # Zero out the first row if needed
    if row_zero:
        for j in range(cols):
            matrix[0][j] = 0
    
    # Zero out the first column if needed
    if col_zero:
        for i in range(rows):
            matrix[i][0] = 0
← Back to All Questions