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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Set Matrix Zeroes

Number: 73

Difficulty: Medium

Paid? No

Companies: Google, Meta, Amazon, Microsoft, Bloomberg, Oracle, Autodesk, Goldman Sachs, Apple, Adobe, Uber, Expedia, Nvidia, tcs, IBM, Sprinklr

Problem Description

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0’s. The transformation must be done in-place without using extra space for another matrix.

Key Insights

  • The challenge is to mark rows and columns that need to be zeroed without using extra space.
  • A common trick is to use the first row and first column as markers.
  • Special care is needed for the first row and first column, as they are also used as markers.
  • The algorithm involves two passes: one for marking and one for updating the matrix based on the markers.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(1) (in-place, using only constant extra space)

Solution

We can solve this problem by using the first row and first column of the matrix as markers. First, determine if the first row or first column needs to be zeroed, then traverse the rest of the matrix and mark the corresponding first row and column positions if a zero is encountered. Finally, update the matrix backward using the markers, and finally update the first row and column if needed.

The algorithm works in three main steps:

  1. Check if the first row or first column should be zeroed (store this in two variables).
  2. Iterate through the rest of the matrix; for any element that is zero, mark its row and column by setting the corresponding element in the first row and first column to zero.
  3. Iterate through the matrix again (excluding the first row and column) and set elements to zero if their row or column marker is zero.
  4. Finally, zero out the first row and/or first column if needed.

This approach avoids extra space usage apart from the two boolean flags while ensuring that the matrix is updated correctly.

Code Solutions

# Python solution for the Set Matrix Zeroes problem

def setZeroes(matrix):
    # Step 1: Determine the dimensions of matrix
    m = len(matrix)
    n = len(matrix[0])
    
    # Determine if first row or first column should be zeroed
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))
    
    # Step 2: Use first row and column as markers
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0  # mark the first element of the row
                matrix[0][j] = 0  # mark the first element of the column
                
    # Step 3: Zero out cells based on the markers in first row and column
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
                
    # Step 4: Zero out the first row if needed
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
            
    # Step 5: Zero out the first column if needed
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0

# Example usage: 
# matrix = [[1,1,1],[1,0,1],[1,1,1]]
# setZeroes(matrix)
# print(matrix)
← Back to All Questions