The O(n) Club: Set Matrix Zeroes — A Griddy Matrix Meltdown

The O(n) Club: Set Matrix Zeroes — A Griddy Matrix Meltdown

⚡ TL;DR

Every zero in your grid? Nuke the whole row and column. The catch: Do it in-place or the interviewer will see you as, well, basic. Standard brute force looks something like this:

// Brute force — a classic "it works, but..."
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (matrix[i][j] == 0) markRowColForLater(i, j);
    }
}
// Later: wipe marked rows and columns

🧠 How Devs Usually Mess This Up

The rookie move: Zero a row or column right when you see a zero. By round two, you’re zeroing things you shouldn’t. That one zero has multiplied faster than your caffeine jitters. And using big marker arrays? Sure, that works — if you never want to brag about O(1) space in an interview.

🔍 What’s Actually Going On

This problem’s not about fancy math—it’s about not shooting yourself in the foot with premature zeroing. The pro move: Turn your first row and column into note-pads—flagging which row or column will need zeroing later. But, heads up: If row 0 or col 0 had a zero to start, you’re balancing markers and actual data on the same ledge. Enter boolean variables: the unsung heroes of grid survival.

🛠️ PseudoCode

• Check if first row/col has any zeros. Set two booleans:
  

  boolean firstRowZero = false, firstColZero = false;

• Scan all other cells:
  On any matrix[i][j]==0 (not first row/col), set matrix[i][0] = 0 and matrix[0][j] = 0.
• Walk through the matrix again—but skip first row/col:
  If a row or col is flagged, matrix[i][j]=0.
• Zero out first row if firstRowZero is true.
• Zero out first column if firstColZero is true.

💻 The Code

public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean firstRowZero = false, firstColZero = false;
    for (int i = 0; i < m; i++) if (matrix[i][0]==0) firstColZero = true;
    for (int j = 0; j < n; j++) if (matrix[0][j]==0) firstRowZero = true;
    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;
            }
    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;
    if (firstRowZero)
        for (int j = 0; j < n; j++) matrix[0][j]=0;
    if (firstColZero)
        for (int i = 0; i < m; i++) matrix[i][0]=0;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Zeroing rows/cols on sight = instant disaster. You lose data before you’re done reading.
• Forgetting about zeros already in the first row/col? Now your precious flags are gone.
• Matrix isn’t square? Relax. This code doesn’t care—it works, but don’t hardcode shortcuts.
• Time: O(mn)—that’s pretty much the best you get.
  Space: O(1), unless you want to keep a diary for each row/col. Don’t.

🧠 Interviewer Brain-Tattoo

“Every grid has secrets. If yours require a second grid to remember the first, you’re thinking too outside the box.”