DSA-009 · In-place row and column markers

Set Matrix Zeroes

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 1519 deterministic checks. Learner drafts are not executed.

Understand the problem

For every zero in the original matrix, set its entire row and column to zero. Perform the update in place without replacing the matrix or its row arrays.

matrix is a non-null rectangular int[][] with 0–100 rows and 0–100 columns. Rows are non-null, equally sized, and distinct array objects; entries are any signed int.
Only original zero positions trigger row/column zeroing. Newly written zeros during this operation must not trigger additional propagation. Empty or zero-column matrices remain unchanged.
Return void and preserve the outer and row array identities. The optimized method uses O(1) auxiliary state by storing markers inside the first row and column.

Examples

Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Only the middle original row and column are zeroed; the four corners remain one.
Input: [[0,1],[2,3]]
Output: [[0,0],[0,3]]
An original top-left zero affects the first row and first column, not the entire matrix.

Before you start

Rectangular matrix bounds and row identities
Separate discovery from destructive updates

Recognize the structure

There are two phases: discover original-zero row/column ownership, then apply it. Immediate propagation destroys the evidence distinguishing original zeros from newly written ones. Input storage can hold row/column flags if boundary metadata is protected.

Try before revealing

Hint 1

What information about the original zero positions must survive mutation?

Hint 2

Separate row flags from column flags.

Hint 3

Use first-row/column markers, preserve their original zero flags, and clear the boundaries last.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Allocate separate row and column flags

First scan the original matrix and record zeroRows[r] and zeroCols[c]. In a second scan, zero cells whose row or column is marked. For [[1,2],[3,0]], the flags mark row 1 and column 1, producing [[1,0],[0,0]]. This is O(RC) time and O(R+C) extra flags, and it preserves every row object.

Improve the baseline

Preserve boundary ownership first

Record whether the original first row and original first column contain any zero using two booleans. Capture them before writing markers.

Use the boundaries as marker arrays

For an interior original zero at (r,c), write matrix[r][0]=0 and matrix[0][c]=0. These positions represent row and column flags, not new propagation sources.

Apply interior updates before boundary updates

Zero interior cells using their two markers. Finally zero the first row or column according to the preserved original flags. Delaying these boundary writes prevents marker corruption.

Why it is correct

Boundary flags

Before any marker writes, the two booleans exactly describe original first-row and first-column zero ownership.

Marker invariant

After the interior discovery scan, a row marker is zero exactly when that row contains an original zero, and a column marker is zero exactly when that column contains an original zero. No interior cell is changed during discovery, so all discovered interior zeros are original.

Application

The interior pass zeroes exactly the union of marked rows and columns. Applying preserved boundary flags completes first-row/column effects without changing any remaining decision. Finite bounded scans terminate, and no array reference is replaced.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

public final class Solution {
    public static void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        if (rows == 0 || matrix[0].length == 0) return;
        int cols = matrix[0].length;
        boolean firstRowZero = false, firstColumnZero = false;
        for (int c = 0; c < cols; c++) if (matrix[0][c] == 0) firstRowZero = true;
        for (int r = 0; r < rows; r++) if (matrix[r][0] == 0) firstColumnZero = true;
        for (int r = 1; r < rows; r++) for (int c = 1; c < cols; c++) {
            if (matrix[r][c] == 0) { matrix[r][0] = 0; matrix[0][c] = 0; }
        }
        for (int r = 1; r < rows; r++) for (int c = 1; c < cols; c++) {
            if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
        }
        if (firstRowZero) for (int c = 0; c < cols; c++) matrix[0][c] = 0;
        if (firstColumnZero) for (int r = 0; r < rows; r++) matrix[r][0] = 0;
    }
    public static void baseline(int[][] matrix) {
        int rows = matrix.length;
        if (rows == 0 || matrix[0].length == 0) return;
        int cols = matrix[0].length;
        boolean[] zeroRows = new boolean[rows], zeroCols = new boolean[cols];
        for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++)
            if (matrix[r][c] == 0) { zeroRows[r] = true; zeroCols[c] = true; }
        for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++)
            if (zeroRows[r] || zeroCols[c]) matrix[r][c] = 0;
    }
}

Read the meaningful blocks

Handle empty dimensions

The code checks rows before reading matrix[0], and columns before using a first-column marker.

Scan the interior only for discovery

Marker cells must not be reinterpreted as fresh zero discoveries.

Delay first row and column clearing

Those locations carry decisions for interior cells until the application scan is done.

Complexity

O(RC) time for a constant number of scans, O(1) auxiliary booleans/indices, and no separate output allocation. Input values change by contract; all array identities remain.

The straightforward flag-array baseline also takes O(RC) time but uses O(R+C) extra storage. Returning a modified copy would have a different mutation and memory contract.

Exact-state walkthroughs

Reveal normal and boundary traces

An interior zero must not erase corners

Input: [[1,1,1],[1,0,1],[1,1,1]] · Final state: [[1,0,1],[0,0,0],[1,0,1]]

Step 1 of 7: Capture original boundary ownership before writing any markers.

The booleans describe original boundary zeros and will never be recomputed from markers.

Matrix values and temporary markers

111

101

111

A highlighted coordinate is the current cell; the state table records boundaries, flags, or output progress.

State after this step
Variable	Value
phase	`"original"`
matrix	`[[1,1,1],[1,0,1],[1,1,1]]`
firstRowZero	`false`
firstColumnZero	`false`

See the affected Java block

 1 public final class Solution {
 2     public static void setZeroes(int[][] matrix) {
 3         int rows = matrix.length;
 4         if (rows == 0 || matrix[0].length == 0) return;
 5         int cols = matrix[0].length;
 6         boolean firstRowZero = false, firstColumnZero = false;
 7         for (int c = 0; c < cols; c++) if (matrix[0][c] == 0) firstRowZero = true;
 8         for (int r = 0; r < rows; r++) if (matrix[r][0] == 0) firstColumnZero = true;
 9         for (int r = 1; r < rows; r++) for (int c = 1; c < cols; c++) {
10             if (matrix[r][c] == 0) { matrix[r][0] = 0; matrix[0][c] = 0; }
11         }
12         for (int r = 1; r < rows; r++) for (int c = 1; c < cols; c++) {
13             if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
14         }
15         if (firstRowZero) for (int c = 0; c < cols; c++) matrix[0][c] = 0;
16         if (firstColumnZero) for (int r = 0; r < rows; r++) matrix[r][0] = 0;
17     }
18     public static void baseline(int[][] matrix) {
19         int rows = matrix.length;
20         if (rows == 0 || matrix[0].length == 0) return;
21         int cols = matrix[0].length;
22         boolean[] zeroRows = new boolean[rows], zeroCols = new boolean[cols];
23         for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++)
24             if (matrix[r][c] == 0) { zeroRows[r] = true; zeroCols[c] = true; }
25         for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++)
26             if (zeroRows[r] || zeroCols[c]) matrix[r][c] = 0;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Capture original boundary ownership before writing any markers.
The booleans describe original boundary zeros and will never be recomputed from markers.
phase
"original"
matrix
[[1,1,1],[1,0,1],[1,1,1]]
firstRowZero
false
firstColumnZero
false
Mark the row and column of an original interior zero.
Interior discovery does not change interior values; boundary zeros now encode ownership.
phase
"markers"
r
1
c
1
matrix
[[1,0,1],[0,0,1],[1,1,1]]
firstRowZero
false
firstColumnZero
false
Complete the marker discovery scan.
Every interior row/column decision is now represented by its boundary marker.
phase
"markers"
matrix
[[1,0,1],[0,0,1],[1,1,1]]
firstRowZero
false
firstColumnZero
false
Apply row/column markers to one interior cell.
Only marked rows or columns are zeroed; boundary markers remain available.
phase
"apply"
r
1
c
1
matrix
[[1,0,1],[0,0,1],[1,1,1]]
firstRowZero
false
firstColumnZero
false
Apply row/column markers to one interior cell.
Only marked rows or columns are zeroed; boundary markers remain available.
phase
"apply"
r
1
c
2
matrix
[[1,0,1],[0,0,0],[1,1,1]]
firstRowZero
false
firstColumnZero
false
Apply row/column markers to one interior cell.
Only marked rows or columns are zeroed; boundary markers remain available.
phase
"apply"
r
2
c
1
matrix
[[1,0,1],[0,0,0],[1,0,1]]
firstRowZero
false
firstColumnZero
false
Final in-place state; the Java method returns void.
The completed state satisfies the declared output and mutation contract.
result
[[1,0,1],[0,0,0],[1,0,1]]

Original boundary zero

Input: [[0,1],[2,3]] · Final state: [[0,0],[0,3]]

Step 1 of 5: Capture original boundary ownership before writing any markers.

The booleans describe original boundary zeros and will never be recomputed from markers.

Matrix values and temporary markers

A highlighted coordinate is the current cell; the state table records boundaries, flags, or output progress.

State after this step
Variable	Value
phase	`"original"`
matrix	`[[0,1],[2,3]]`
firstRowZero	`true`
firstColumnZero	`true`

See the affected Java block

 1 public final class Solution {
 2     public static void setZeroes(int[][] matrix) {
 3         int rows = matrix.length;
 4         if (rows == 0 || matrix[0].length == 0) return;
 5         int cols = matrix[0].length;
 6         boolean firstRowZero = false, firstColumnZero = false;
 7         for (int c = 0; c < cols; c++) if (matrix[0][c] == 0) firstRowZero = true;
 8         for (int r = 0; r < rows; r++) if (matrix[r][0] == 0) firstColumnZero = true;
 9         for (int r = 1; r < rows; r++) for (int c = 1; c < cols; c++) {
10             if (matrix[r][c] == 0) { matrix[r][0] = 0; matrix[0][c] = 0; }
11         }
12         for (int r = 1; r < rows; r++) for (int c = 1; c < cols; c++) {
13             if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
14         }
15         if (firstRowZero) for (int c = 0; c < cols; c++) matrix[0][c] = 0;
16         if (firstColumnZero) for (int r = 0; r < rows; r++) matrix[r][0] = 0;
17     }
18     public static void baseline(int[][] matrix) {
19         int rows = matrix.length;
20         if (rows == 0 || matrix[0].length == 0) return;
21         int cols = matrix[0].length;
22         boolean[] zeroRows = new boolean[rows], zeroCols = new boolean[cols];
23         for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++)
24             if (matrix[r][c] == 0) { zeroRows[r] = true; zeroCols[c] = true; }
25         for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++)
26             if (zeroRows[r] || zeroCols[c]) matrix[r][c] = 0;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Capture original boundary ownership before writing any markers.
The booleans describe original boundary zeros and will never be recomputed from markers.
phase
"original"
matrix
[[0,1],[2,3]]
firstRowZero
true
firstColumnZero
true
Complete the marker discovery scan.
Every interior row/column decision is now represented by its boundary marker.
phase
"markers"
matrix
[[0,1],[2,3]]
firstRowZero
true
firstColumnZero
true
Clear the first row according to its original flag.
Interior decisions are complete, so row-marker storage is no longer needed.
phase
"boundary"
matrix
[[0,0],[2,3]]
firstRowZero
true
firstColumnZero
true
Clear the first column according to its original flag.
All output cells now match the original-zero row/column rule.
phase
"boundary"
matrix
[[0,0],[0,3]]
firstRowZero
true
firstColumnZero
true
Final in-place state; the Java method returns void.
The completed state satisfies the declared output and mutation contract.
result
[[0,0],[0,3]]

Test the contract

Input: []
Output: []
No rows.
Input: [[]]
Output: [[]]
No columns.
Input: [[1,0,3]]
Output: [[0,0,0]]
One row.
Input: [[1],[0],[3]]
Output: [[0],[0],[0]]
One column.

Common mistakes and counterexamples

Zero rows while still discovering original zeros

Counterexample: A center zero can spread to the whole matrix instead of leaving corners unchanged.

Separate discovery and application.

Derive boundary flags after writing markers

Counterexample: A center zero creates first-row markers even if the original first row had no zeros.

Capture both original boundary facts first.

Clear the first row too early

Counterexample: Its column markers are still needed by interior rows.

Apply boundary flags last.

Assume repeated calls must be idempotent

Counterexample: A second call sees the first call’s new zeros as original input and may zero more cells.

Compute the oracle from the pre-call snapshot for each invocation.

Follow-ups

Input must be preserved.

Return a deep copy and apply the operation there; count O(RC) output storage explicitly. An outer clone still aliases rows.

Zero cells according to another trigger value.

Marker choice can collide with ordinary data. Use separate flags or prove an unambiguous in-place encoding under a restricted domain; do not assume an unused sentinel exists.

Rows may share the same array object.

The ordinary independent-cell mutation model no longer applies: writing one row changes another alias. Reject aliases, clone them, or define observable behavior explicitly before reusing this solution.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 100/20,000 characters

Self-review

I preserve original-zero information before writing.I distinguish markers from propagation sources.I preserve row identities and state mutation explicitly.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Review the prerequisites above and the related problems below.

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-15 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These are standard algorithmic tasks; no company-frequency or interview-outcome claims are made.