Algorithm-Day18-Set-Matrix-Zeroes-lc-73

Posted on In , Views:

🧩 Problem Description

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

Example:

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

💡 Brute Force (Not Ideal)

  • Mark all rows and columns with zeros using extra sets.
  • Time: O(m × n)
  • Space: O(m + n) → uses extra memory, not fully in-place.

💡 Optimal Approach: Constant Space Using First Row and Column

✨ Key Idea

  • Use the first row and first column as markers for rows and columns that need to be zeroed.
  • Two passes:
    1. Mark rows/columns.
    2. Set cells to zero based on markers.
  • Special care is needed for handling the first row and column separately.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean firstRowZero = false;
        boolean firstColZero = false;

        // Check if first row needs to be zeroed
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }

        // Check if first column needs to be zeroed
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }

        // Use first row and column as markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // Zero cells based on markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Zero first row if needed
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }

        // Zero first column if needed
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(m × n)
    Two passes over the matrix.
  • Space Complexity: O(1)
    No extra space beyond the matrix itself.

✍️ Summary

  • Smart use of the matrix itself as storage avoids extra space usage.
  • Watch out for the first row and first column edge cases.
  • Similar in-place patterns appear in other matrix transformation problems.

Learning how to reuse input space for flags is a useful technique in constrained-space algorithm design.