Cracking The Coding Interview Together – Problem 1.8: Zero Matrix

I hope you are doing good and are enjoying this series. Today's discussion topic i.e. Zero Matrix is interesting, simple but with a small caveat that can be easily overlooked, if you are not cautious. Let's get into it and dissect the problem.

Let’s get into today's problem! We always follow the format as follows

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem statement

Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0

Analyse the problem statement together

Let’s read the prompt slowly and make sure we both see the same thing. We have a matrix with M rows and N columns. Whenever any cell contains a 0, the requirement is to set every cell in that cell’s row and that cell’s column to 0. The final matrix should reflect zeroing for all original zeros.

Important clarifications implied by the question:

• The change should be based on the original zero positions. In other words, zeroes created by your own mutations should not cause additional zeroing.
• Ideally we’re asked if this can be done in place — i.e., using the same matrix and O(1) extra space, if possible.
• Typical input: integers, zeros and non-zero values.

Example:

Input:

1 2 3
4 0 6
7 8 9

Output:

1 0 3
0 0 0
7 0 9

Take some time and try to dig deep to see if there is anything unclear to you.

Questions for the interviewer

Every good interview solution starts with the right questions. If I were sitting in front of an interviewer, I’d ask:

Always ask these aloud — interviewer likes it:

1. Can we assume the matrix is non-null and rectangular (each row has same number of columns)?
   (If not guaranteed, we’d validate inputs; assume yes for the core algorithm.)
2. Do we need to do this in place?
   (The problem asks — prefer O(1) extra space if possible; but I’d present both O(M+N) and O(1) solutions.)
3. What about memory constraints / large matrices?
   (If memory is tight, O(1) approach is required.)
4. Are we allowed to modify the matrix as we scan, or must we base changes on the original state?
   (We must base changes on the original zeros — otherwise mutation will cascade.)
5. Edge cases: single row/column, all zeros, no zeros?
   (We will test those.)

These questions show you’re thoughtful. Assume interviewer says: yes rectangular, prefer in-place if possible, base on original state.

Think about the Solution

Take a minute. Try to reason it out on paper or in your head. Don’t skip this — verbalizing your approach is the single biggest indicator of interview readiness. Think about:

• If you mark rows and columns as you see zeros, will later reads be polluted?
• What data structure can hold which rows/columns to zero out later?
• Can you reuse the matrix itself to store that information?

Pause now. I’ll wait.

Alright — let’s reason through options out loud.

Brute-force (wrong if mutated immediately):
Walk matrix; when you encounter zero, immediately set that entire row and column to zero. Problem: you will zero cells that you haven’t yet visited, causing newly written zeros to trigger more zeroing. This over-propagates — incorrect.

Safe simple approach (two-pass with extra memory):

• First pass: record which rows and which columns contain zeros. Use two boolean arrays: rows[M] and cols[N].
• Second pass: iterate again, if rows[i] or cols[j] is true, set matrix[i][j] = 0.

This is simple, correct, and readable. Space: O(M + N). Time: O(M*N). Good answer if in-place not required.

In-place approach (O(1) extra space): (the interviewer’s favorite)

Key idea: use the first row and first column of the matrix to store markers for which columns/rows should be zeroed. But careful: if the first row or first column already has original zeros, we need to remember that separately (two boolean flags). Steps:

1. Scan first row to see if it has any zeros → firstRowZero.
2. Scan first column to see if it has any zeros → firstColZero.
3. For all other cells (i,j) (i>0, j>0), if matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0.
4. Use the markers in row 0 and column 0 to set matrix cells to zero (skip row0/col0 initially).
5. Finally, if firstRowZero was true, zero out row 0. If firstColZero was true, zero out column 0.

This uses the matrix itself as metadata and uses only two booleans extra: O(1) extra space.

Write code and explain

Approach 1: Safe Simple Approach

We make one pass through the matrix, record which rows and columns contain zeros, and then make another pass to zero out everything that belongs to those rows/columns. No risk of cascading mutations. Very easy to reason about.

Implementation could be as follows:

public static void setZeroesSafe(int[][] matrix) {
    if (matrix == null || matrix.length == 0) return;

    int rows = matrix.length;
    int cols = matrix[0].length;

    boolean[] zeroRows = new boolean[rows];  // rows to be zeroed
    boolean[] zeroCols = new boolean[cols];  // columns to be zeroed

    // 1. First pass: mark rows and columns that contain a zero
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == 0) {
                zeroRows[i] = true;
                zeroCols[j] = true;
            }
        }
    }

    // 2. Second pass: zero rows
    for (int i = 0; i < rows; i++) {
        if (zeroRows[i]) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = 0;
            }
        }
    }

    // 3. Third pass: zero columns
    for (int j = 0; j < cols; j++) {
        if (zeroCols[j]) {
            for (int i = 0; i < rows; i++) {
                matrix[i][j] = 0;
            }
        }
    }
}

Time & space complexity

1. We must touch each element two times which effectively translates to O(M*N)
2. Everything is done in-place with only temporary array - O(M+N)

Approach 2: In place and efficient

public static void setZeroes(int[][] matrix) {
    if (matrix == null || matrix.length == 0) return;

    int rows = matrix.length;
    int cols = matrix[0].length;

    boolean firstRowZero = false;
    boolean firstColZero = false;

    // 1. Check if first row has zero
    for (int j = 0; j < cols; j++) {
        if (matrix[0][j] == 0) {
            firstRowZero = true;
            break;
        }
    }

    // 2. Check if first column has zero
    for (int i = 0; i < rows; i++) {
        if (matrix[i][0] == 0) {
            firstColZero = true;
            break;
        }
    }

    // 3. Use first row and column to mark zeros for other cells
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0; // mark row
                matrix[0][j] = 0; // mark column
            }
        }
    }

    // 4. Zero cells based on marks in first row and column
    // Zero rows based on column 0
    for (int i = 1; i < rows; i++) {
        if (matrix[i][0] == 0) {
            for (int j = 1; j < cols; j++) {
                matrix[i][j] = 0;
            }
        }
    }

    // Zero columns based on row 0
    for (int j = 1; j < cols; j++) {
        if (matrix[0][j] == 0) {
            for (int i = 1; i < rows; i++) {
                matrix[i][j] = 0;
            }
        }
    }

    // 5. Finally zero first row / first column if required
    if (firstRowZero) {
        for (int j = 0; j < cols; j++) {
            matrix[0][j] = 0;
        }
    }

    if (firstColZero) {
        for (int i = 0; i < rows; i++) {
            matrix[i][0] = 0;
        }
    }
}

Explain aloud while coding:

• Validate inputs first — defensive check.
• firstRowZero and firstColZero capture whether we must clear those header lines at the end.
• We purposely start marking from i=1, j=1 to avoid disturbing header metadata.
• After marking, we apply changes based on markers — again starting from 1 to avoid early mutation of markers.
• Finally, we clean up the header row and column if needed.

This step-by-step tells the interviewer you can separate discovery and mutation, and you can compress metadata in-place without extra arrays.

Time & space complexity — say it clearly

• Time: O(M * N) — you visit each cell a constant number of times (scan, mark, apply).
• Space: O(1) extra — only two boolean flags in addition to the input matrix.

Final Thoughts

This problem is deceptively simple. Interviewers are checking whether you:

• Recognize side effects of in-place mutation while scanning
• Separate analysis from mutation
• Can compress state into the input safely (use matrix as metadata)
• Handle boundary conditions (first row/col)
• Communicate the approach clearly

When you explain this in an interview, be explicit about the discovery → mark → apply phases. That clarity demonstrates engineering maturity — not just algorithmic recall.

Happy Coding!