Set Matrix Zeros

Problem Link

Set Matrix Zeroes – LeetCode

Problem: Set Matrix Zeroes

Problem Statement

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0.

You must do it in place, without using extra space for another matrix.

Examples

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
-2³¹ <= matrix[i][j] <= 2³¹ - 1

Intuition

If a cell contains 0, we want to zero out both its row and column.
The challenge is to do this in-place, without affecting the rest of the matrix prematurely.

Brute Force Approach

Approach

Traverse the matrix and store all coordinates of zeroes.
For each stored coordinate (i, j), set the entire iᵗʰ row and jᵗʰ column to 0.

Code (Brute Force – O(mn*(m+n)))

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        List<int[]> zeroes = new ArrayList<>();

        // Step 1: Record zero positions
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    zeroes.add(new int[]{i, j});
                }
            }
        }

        // Step 2: Set corresponding rows and columns to 0
        for (int[] pos : zeroes) {
            int row = pos[0], col = pos[1];
            for (int i = 0; i < m; i++) matrix[i][col] = 0;
            for (int j = 0; j < n; j++) matrix[row][j] = 0;
        }
    }
}

Time & Space Complexity

Time: O(mn * (m + n))
Space: O(mn) (for storing all zero positions)

Optimal Approach (Constant Space)

Idea

Use the first row and first column as markers to track which rows and columns should be zeroed.

Special Handling

Use a separate variable colz to track if the first column should be zeroed (since matrix[0][0] is shared by both row and column markers).

Code (Optimal – In-Place)

class Solution {
    public void setZeroes(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        int colz = 1; // Whether first column needs to be zeroed

        // Step 1: Use first row/column as markers
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    mat[i][0] = 0; // Mark row
                    if (j == 0) {
                        colz = 0;
                    } else {
                        mat[0][j] = 0; // Mark column
                    }
                }
            }
        }

        // Step 2: Set cells to 0 based on markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (mat[i][0] == 0 || mat[0][j] == 0) {
                    mat[i][j] = 0;
                }
            }
        }

        // Step 3: First row
        if (mat[0][0] == 0) {
            for (int j = 0; j < n; j++) {
                mat[0][j] = 0;
            }
        }

        // Step 4: First column
        if (colz == 0) {
            for (int i = 0; i < m; i++) {
                mat[i][0] = 0;
            }
        }
    }
}

Time and Space Complexity

Time Complexity: O(m × n)
Space Complexity: O(1) (in-place with constant extra space)

Dry Run

Input:

matrix = [[0,1,2,0],
          [3,4,5,2],
          [1,3,1,5]]

Step 1: Mark rows and columns

At (0,0) → matrix[0][0] = 0 → mark row 0 and column 0
    
At (0,3) → matrix[0][3] = 0 → mark row 0 and column 3

Markers after Step 1:

matrix = [[0,1,2,0],
          [3,4,5,2],
          [1,3,1,5]]
colz = 0

Step 2: Apply markers to set 0s

Start from (1,1):

- matrix[1][0] != 0 and matrix[0][1] != 0 → skip
    
- matrix[1][1] → OK
    
- matrix[1][2] → OK
    
- matrix[1][3] → matrix[0][3] == 0 → set to 0
    

Row 2:

- matrix[2][0] != 0 and matrix[0][1/2/3] → column 3 is marked → matrix[2][3] = 0

Matrix after Step 2:

[[0,1,2,0],
 [3,4,5,0],
 [1,3,1,0]]

Step 3: First row

matrix[0][0] == 0 → zero entire first row

Result:

[[0,0,0,0],
 [3,4,5,0],
 [1,3,1,0]]

Step 4: First column

colz == 0 → zero entire first column

Final Output:

[[0,0,0,0],
 [0,4,5,0],
 [0,3,1,0]]

Conclusion

This problem is a classic example of matrix in-place manipulation. The brute-force solution is simple but inefficient. The optimal solution cleverly reuses the matrix itself to reduce space complexity to O(1) without sacrificing correctness.