Definition
- Set Matrix Zeroes – if any cell in an m-by-n matrix is zero, its entire row and entire column must be set to zero.
- In-place markers – the first row and first column are reused as marker storage, recording which rows and columns need zeroing.
- Saved flags – two boolean flags record whether the first row and first column originally contained a zero, since they are about to be overwritten with markers.
- Four phases – (1) save flags, (2) mark using first row/column, (3) zero inner cells, (4) zero first row/column.
- Complexity – O(m * n) time, O(1) extra space.
At the National Bank of India, a reconciliation grid has rows for dates and columns for branches. A zero means a frozen entry. Policy requires the entire date (row) and entire branch (column) to be wiped. Instead of a separate notepad, Priya writes the flags in the margin of the grid itself, the top row and left column, then wipes in one careful pass.
Understanding the Concepts
What is the Set Matrix Zeroes problem?
Given an m-by-n matrix, if any cell is zero, set its entire row and entire column to zero. The challenge is to do it in place using O(1) extra space. The naive approach copies the matrix or keeps separate sets of row and column indices, costing O(m+n) extra space.
package com.bank.service;
public class SetMatrixZeroes {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean firstRowZero = false, firstColZero = false;
// Phase 1: save flags
for (int j = 0; j < n; j++)
if (matrix[0][j] == 0) firstRowZero = true;
for (int i = 0; i < m; i++)
if (matrix[i][0] == 0) firstColZero = true;
// Phase 2: mark using first row/column
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;
}
// Phase 3: zero inner cells
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;
// Phase 4: zero first row and column
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;
}
}
Why use the first row and column as markers?
Instead of allocating separate arrays or sets to record which rows and columns must be zeroed, we reuse the first row and first column of the matrix itself. When we find matrix[i][j] == 0, we set matrix[i][0] = 0 (mark the row) and matrix[0][j] = 0 (mark the column). This saves O(m+n) space.
// Instead of:
Set<Integer> zeroRows = new HashSet<>(); // O(m) space
Set<Integer> zeroCols = new HashSet<>(); // O(n) space
// We use:
matrix[i][0] = 0; // marks row i for zeroing
matrix[0][j] = 0; // marks col j for zeroing
// Only O(1) extra space for the two boolean flags
Why do we need the two boolean flags?
Before writing markers into the first row and column, we must check whether those rows and columns originally contained a zero. If we skip this step, we cannot tell whether a zero in the first row or column was an original zero or a marker we wrote. The flags capture the original state before we modify anything.
package com.bank.service;
public class FlagDemo {
public static void main(String[] args) {
int[][] matrix = {
{0, 1, 1},
{1, 1, 1},
{1, 1, 0}
};
// First row contains a zero at [0][0] -> firstRowZero = true
// First col contains a zero at [0][0] -> firstColZero = true
// Without flags, we would not know if matrix[0][0]=0 was
// original or a marker from matrix[2][2]=0
boolean firstRowZero = false;
for (int j = 0; j < 3; j++)
if (matrix[0][j] == 0) { firstRowZero = true; break; }
System.out.println("First row has zero: " + firstRowZero); // true
}
}
First row has zero: true
Why does the order of phases matter?
If we zeroed the first row and column before processing the inner cells, we would destroy the markers and zero the entire matrix. The correct order is: save flags, mark, zero inner cells, then zero first row and column.
// WRONG ORDER: zeroing first row/col before inner cells
// destroys markers -> entire matrix becomes zero
// CORRECT ORDER:
// Phase 1: Save flags (firstRowZero, firstColZero)
// Phase 2: Mark (write zeros into first row/col)
// Phase 3: Zero inner cells (read markers, zero cells)
// Phase 4: Zero first row/col (use saved flags)
What is the time and space complexity?
The matrix is traversed a constant number of times (about 3-4 passes), so time is O(m * n). Only two boolean variables are used for extra space.
- Time complexity – O(m * n), each cell visited a constant number of times.
- Space complexity – O(1) extra, using only two boolean flags.
- Comparison – the naive approach uses O(m + n) for row and column index sets.
// Phase 1: O(m + n) to check first row and column
// Phase 2: O(m * n) to scan inner matrix and mark
// Phase 3: O(m * n) to zero inner cells
// Phase 4: O(m + n) to zero first row/column
// Total: O(m * n)
What are the edge cases?
Edge cases include a matrix with no zeros (nothing changes), a matrix that is entirely zero, a single-row or single-column matrix, and the case where the zero is only in the first row or first column.
package com.bank.service;
public class ZeroEdgeCases {
public static void main(String[] args) {
SetMatrixZeroes solver = new SetMatrixZeroes();
// No zeros: nothing changes
int[][] m1 = {{1,2},{3,4}};
solver.setZeroes(m1);
System.out.println(java.util.Arrays.deepToString(m1));
// [[1, 2], [3, 4]]
// Single row with zero
int[][] m2 = {{1, 0, 3}};
solver.setZeroes(m2);
System.out.println(java.util.Arrays.deepToString(m2));
// [[0, 0, 0]]
}
}
[[1, 2], [3, 4]]
[[0, 0, 0]]
What are common mistakes?
The most common mistake is zeroing the first row and column before using the markers to zero inner cells. Another mistake is not saving the boolean flags before the marking phase, causing the original state of the first row and column to be lost.
// WRONG: zero first row/col too early
if (firstRowZero)
for (int j = 0; j < n; j++) matrix[0][j] = 0; // destroys 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; // reads destroyed markers!
// CORRECT: zero inner cells FIRST, then first row/col
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;
How would you apply this in a banking system?
At the National Bank of India, a reconciliation grid has rows for dates and columns for branches. A zero means a detected discrepancy that policy requires quarantining across the whole date and the whole branch before filing. The in-place marker technique processes large grids without allocating a second matrix.
package com.bank.service;
public class ReconciliationQuarantine {
public void quarantineDiscrepancies(int[][] grid) {
// Reuse first row/col as markers
int m = grid.length, n = grid[0].length;
boolean firstRowFlag = false, firstColFlag = false;
for (int j = 0; j < n; j++)
if (grid[0][j] == 0) firstRowFlag = true;
for (int i = 0; i < m; i++)
if (grid[i][0] == 0) firstColFlag = true;
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
if (grid[i][j] == 0) {
grid[i][0] = 0;
grid[0][j] = 0;
}
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
if (grid[i][0] == 0 || grid[0][j] == 0)
grid[i][j] = 0;
if (firstRowFlag)
for (int j = 0; j < n; j++) grid[0][j] = 0;
if (firstColFlag)
for (int i = 0; i < m; i++) grid[i][0] = 0;
}
}
What should a senior engineer know?
A senior engineer should know the four-phase approach and the critical ordering constraint. They should also recognise that a single-flag variant exists where matrix[0][0] serves as the row-zero flag and only one extra boolean is needed for the column, but this is harder to reason about and error-prone. The two-flag version is clearer and safer.
// Single-flag variant (trickier):
// matrix[0][0] is shared by first row and first col.
// Use matrix[0][0] for first row, separate flag for first col.
// Process first col flag BEFORE marking to avoid corruption.
// Two-flag version is simpler and less error-prone.
Visual Overview
Original Matrix: ┌───┬───┬───┐ │ 1 │ 1 │ 1 │ ├───┼───┼───┤ │ 1 │ 0 │ 1 │ ← zero at [1][1] ├───┼───┼───┤ │ 1 │ 1 │ 1 │ └───┴───┴───┘ Phase 1: Save flags firstRowZero = false, firstColZero = false Phase 2: Mark (write into first row/col) matrix[1][0] = 0 (row 1 marker) matrix[0][1] = 0 (col 1 marker) ┌───┬───┬───┐ │ 1 │ 0 │ 1 │ ← col marker ├───┼───┼───┤ │ 0 │ 0 │ 1 │ ← row marker ├───┼───┼───┤ │ 1 │ 1 │ 1 │ └───┴───┴───┘ Phase 3: Zero inner cells using markers ┌───┬───┬───┐ │ 1 │ 0 │ 1 │ ├───┼───┼───┤ │ 0 │ 0 │ 0 │ ← row 1 zeroed ├───┼───┼───┤ │ 1 │ 0 │ 1 │ ← col 1 zeroed └───┴───┴───┘ Phase 4: First row/col (flags were false, skip) Final result: same as above
Key Takeaway
Set Matrix Zeroes requires that if any cell is zero, its entire row and column are zeroed, and the in-place challenge is doing this with only constant extra space. The elegant technique reuses the first row and first column as marker storage, recording which rows and columns need zeroing without allocating separate sets.
The algorithm has four phases. First, I save two boolean flags for whether the first row and first column originally contain a zero. Second, I scan the inner matrix and mark zeros into the first row and column. Third, I zero inner cells based on those markers. Fourth, I use the saved flags to decide whether to zero the first row and column themselves.
The order is critical. If I zeroed the first row or column before using the markers, I would destroy the information I need for the inner cells. The two-flag approach is clearer and less error-prone than the single-flag variant. The entire algorithm runs in O(m * n) time with O(1) extra space.
At the National Bank of India, a reconciliation grid had rows for dates and columns for branches, and a zero meant a discrepancy requiring quarantine across the whole date and branch. The in-place marker technique kept the nightly reconciliation job within its memory budget.
Remember one sentence: save two flags, mark into the first row and column, zero the inner cells, then zero the borders last.
---