{x}
blog image

Set Matrix Zeroes

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.

 

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

 

Constraints:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -231 <= matrix[i][j] <= 231 - 1

 

Follow up:

  • A straightforward solution using O(mn) space is probably a bad idea.
  • A simple improvement uses O(m + n) space, but still not the best solution.
  • Could you devise a constant space solution?

73. Set Matrix Zeroes

Problem Description

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

Solution Approaches and Code

This problem can be solved using two main approaches:

Approach 1: Using Auxiliary Arrays

This approach utilizes two boolean arrays, row and col, to track rows and columns that need to be set to zero. The first pass identifies which rows and columns contain zeros. The second pass sets the elements accordingly.

Time Complexity: O(m*n) due to two traversals of the matrix. Space Complexity: O(m+n) due to the auxiliary arrays.

Python:

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    row = [False] * m
    col = [False] * n
 
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                row[i] = True
                col[j] = True
 
    for i in range(m):
        for j in range(n):
            if row[i] or col[j]:
                matrix[i][j] = 0

Java:

public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean[] row = new boolean[m];
    boolean[] col = new boolean[n];
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) {
                row[i] = true;
                col[j] = true;
            }
        }
    }
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (row[i] || col[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

Approach 2: In-Place Marking

This optimized approach cleverly uses the first row and first column of the matrix itself to store the information about which rows and columns need to be zeroed. It requires handling the case where the first row or column itself needs to be zeroed separately.

Time Complexity: O(m*n) - Similar to Approach 1, but avoids extra space. Space Complexity: O(1) - Constant extra space.

Python:

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row_zero = False
    first_col_zero = False
 
    # Check if first row and column have zeros
    for i in range(m):
        if matrix[i][0] == 0:
            first_col_zero = True
            break
    for j in range(n):
        if matrix[0][j] == 0:
            first_row_zero = True
            break
 
    # Mark rows and cols using first row and col
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
 
    # Set zeros based on marks in first row and col
    for i in range(1, m):
        if matrix[i][0] == 0:
            for j in range(n):
                matrix[i][j] = 0
    for j in range(1, n):
        if matrix[0][j] == 0:
            for i in range(m):
                matrix[i][j] = 0
 
    # Set first row and col to zero if necessary
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0

Java: (Similar logic as Python, but with Java syntax)

Other languages like C++, JavaScript, Go, TypeScript, Rust, and C# can implement both approaches with similar time and space complexities. The core logic remains the same, only the syntax changes. For brevity, I've omitted the full code for all languages here. However, you can adapt the Python or Java examples provided to the specific syntax of your preferred language.