Skip to content
AI360Xpert
Back to Math & Geometry
Medium

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.

Examples

Input:matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output:[[1,0,1],[0,0,0],[1,0,1]]
The 0 at (1,1) causes row 1 and column 1 to become all 0s.
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]]
The 0s at (0,0) and (0,3) cause row 0, column 0, and column 3 to become all 0s.

Constraints

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

In-place using first row/col as markers

Approach

To achieve O(1) space, we can use the first row and first column of the matrix itself to keep track of which rows and columns need to be set to zero. However, the first element `matrix[0][0]` represents both the first row and the first column. To resolve this ambiguity, we use an extra variable `rowZero` to indicate if the first row needs to be zeroed out. 1. Iterate over the matrix. If `matrix[r][c] == 0`, set `matrix[0][c] = 0`. If `r > 0`, set `matrix[r][0] = 0`. If `r == 0`, set `rowZero = true`. 2. Iterate over the matrix again (skipping the first row and col, starting from `(1,1)`). If `matrix[0][c] == 0` or `matrix[r][0] == 0`, set `matrix[r][c] = 0`. 3. Finally, zero out the first column if `matrix[0][0] == 0`, and zero out the first row if `rowZero == true`.

Complexity Analysis

Time Complexity
O(m * n)
Space Complexity
O(1)

This approach requires iterating over the matrix twice, which takes O(m * n) time. Since we only use one boolean variable `rowZero`, the extra space is O(1).

Solution.java
class Solution {    public void setZeroes(int[][] matrix) {        int m = matrix.length;        int n = matrix[0].length;        boolean rowZero = false;                // Step 1: Determine which rows and columns need to be zeroed        for (int r = 0; r < m; r++) {            for (int c = 0; c < n; c++) {                if (matrix[r][c] == 0) {                    matrix[0][c] = 0;                    if (r > 0) {                        matrix[r][0] = 0;                    } else {                        rowZero = true;                    }                }            }        }                // Step 2: Zero out cells based on markers in first row and column        for (int r = 1; r < m; r++) {            for (int c = 1; c < n; c++) {                if (matrix[0][c] == 0 || matrix[r][0] == 0) {                    matrix[r][c] = 0;                }            }        }                // Step 3: Zero out the first column if needed        if (matrix[0][0] == 0) {            for (int r = 0; r < m; r++) {                matrix[r][0] = 0;            }        }                // Step 4: Zero out the first row if needed        if (rowZero) {            for (int c = 0; c < n; c++) {                matrix[0][c] = 0;            }        }    }}