Log inSign up
mediumLeetCodeNot Started

Set Matrix Zeroes

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in-place without allocating an auxiliary full matrix.

---

### Constraints: - m == matrix.length - n == matrix[0].length - 1 <= m, n <= 200 - -2^31 <= matrix[i][j] <= 2^31 - 1

---

### Follow-up Questions: - A straightforward solution using **O(m * n) space is probably a bad idea. - A simple improvement uses O(m + n) space, but can you do it in O(1)** constant auxiliary space?

Example 1 · Example 1 (Single Interior Zero):

Input: matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output: [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
Explanation: Element at row 1, col 1 is 0. Its entire row (row 1) and entire column (col 1) are set to 0.

Example 2 · Example 2 (Multiple Border Zeroes):

Input: matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
Output: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
Explanation: Zeroes at (0, 0) and (0, 3) cause row 0, col 0, and col 3 to be set to 0.

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array Indexing
  • Basic Time & Space Complexity Analysis

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why in-place modifications require decoupled discovery and execution phases.
  • Master the technique of embedding marker tables into the data structure itself.
  • Resolve coordinate overlap conflicts (matrix[0][0]) using dedicated scalar state variables.
  • Implement production-ready solutions in C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • In-place 2D grid modification requirement with strict O(1) auxiliary memory.
  • Grid elements trigger row-wide or column-wide mutations.
  • Need to decouple the scanning phase from the mutation phase without extra memory buffers.

Algorithmic Decision Tree:

  • If allowed O(M + N) space: Use two boolean arrays rowZero[m] and colZero[n].
  • If strictly O(1) auxiliary space: Embed marker arrays directly inside matrix[r][0] and matrix[0][c], with col0 scalar for overlap.

Connected Patterns:

Game of Life: State encoding with temporary bit masks.Rotate Image: In-place diagonal transpose followed by row reversal.Spiral Matrix: Inward boundary contraction.

1. Full Matrix Clone & Reference

Intuition

Create an M x N copy of the matrix to read original zero locations without interference, and write zeroes to the original matrix.

Algorithm

  1. 1. Allocate a duplicate matrix clone of size M x N and copy all values from matrix.
  2. 2. Iterate over each cell (r, c) in the clone matrix.
  3. 3. If clone[r][c] == 0, iterate across row r (0..N-1) and column c (0..M-1) in the original matrix and set matrix[r][k] = 0 and matrix[k][c] = 0.
  4. 4. The original matrix is now updated without any chain-reaction corruption.

Brute Force Sentinel Replacement Scan

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [1, 1, 1, 1, 0, 1, 1, 1, 1]
Current operationSTEP 1 OF 7
Phase 1 — Trigger sentinel marking for row 1 and column 1: Step 1: Traverse matrix cells
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
1
1
r1
1
0
↑ Zero at (1, 1)
1
r2
1
1
1
Variables at this step
r
1
c
1
Val
0
Action
Mark Row 1 & Col 1
Check / comparison
matrix[1][1] == 0. Found zero at row 1, col 1.
Decision / next transition
Trigger sentinel marking for row 1 and column 1.
Why this step matters

Phase 1 — Trigger sentinel marking for row 1 and column 1: Step 1: Traverse matrix cells. At coordinate (1, 1), a zero is detected.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 void setZeroes(vector<vector<int>>& matrix) {
17 int m = matrix.size();
18 int n = matrix[0].size();
19 vector<vector<int>> clone = matrix;
20
21 for (int r = 0; r < m; ++r) {
22 for (int c = 0; c < n; ++c) {
23 if (clone[r][c] == 0) {
24 for (int k = 0; k < n; ++k) matrix[r][k] = 0;
25 for (int k = 0; k < m; ++k) matrix[k][c] = 0;
26 }
27 }
28 }
29 }
30};
31
32int main() {
33 Solution sol;
34 vector<vector<int>> matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
35 sol.setZeroes(matrix);
36 cout << "Matrix After setZeroes:" << endl;
37 for (const auto& row : matrix) {
38 for (int val : row) cout << val << " ";
39 cout << endl;
40 }
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(M * N * (M + N)) — We scan M x N cells. For each zero found, we perform O(M + N) work to overwrite the row and column in the original matrix. In the worst case (all zeroes), this takes O(M * N * (M + N)) time.
  • Space complexity: O(M * N) — Requires an auxiliary matrix clone of dimensions M x N, consuming O(M * N) additional memory.

Why Brute Force Doesn't Scale:

In an M x N grid, we only need to store M boolean flags for rows and N boolean flags for columns. Instead of creating new arrays, matrix[0][c] has N cells and matrix[r][0] has M cells. By reusing these existing border cells as our flags and reserving a single scalar variable for column 0, auxiliary memory drops to zero.

For a 200 x 200 grid: Brute force uses 40,000 ints (~160 KB). Optimal uses 0 extra bytes.

2. Row & Column Marker Arrays

Intuition

Maintain two separate boolean arrays (zeroRows of size M and zeroCols of size N) to record which rows and columns must be zeroed.

Algorithm

  1. 1. Allocate boolean array zeroRows of length M and zeroCols of length N initialized to false.
  2. 2. First pass: Scan matrix[r][c]. If cell is 0, set zeroRows[r] = true and zeroCols[c] = true.
  3. 3. Second pass: Scan matrix[r][c]. If zeroRows[r] || zeroCols[c] is true, set matrix[r][c] = 0.
  4. 4. The matrix is updated in O(M * N) time with O(M + N) auxiliary space.

Row & Column Auxiliary Flag Arrays

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [1, 1, 1, 1, 0, 1, 1, 1, 1]
Current operationSTEP 1 OF 7
Phase 1 — Begin first pass to flag zero locations: Step 1: Use two 1D arrays to keep track of rows and columns that must become zero
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
1
1
r1
1
0
1
r2
1
1
1
Variables at this step
rowMarker
[0, 0, 0]
colMarker
[0, 0, 0]
Check / comparison
Initialize rowMarker = [0, 0, 0] (size M) and colMarker = [0, 0, 0] (size N).
Decision / next transition
Begin first pass to flag zero locations.
Why this step matters

Phase 1 — Begin first pass to flag zero locations: Step 1: Use two 1D arrays to keep track of rows and columns that must become zero.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 void setZeroes(vector<vector<int>>& matrix) {
17 int m = matrix.size();
18 int n = matrix[0].size();
19 vector<bool> zeroRows(m, false);
20 vector<bool> zeroCols(n, false);
21
22 for (int r = 0; r < m; ++r) {
23 for (int c = 0; c < n; ++c) {
24 if (matrix[r][c] == 0) {
25 zeroRows[r] = true;
26 zeroCols[c] = true;
27 }
28 }
29 }
30
31 for (int r = 0; r < m; ++r) {
32 for (int c = 0; c < n; ++c) {
33 if (zeroRows[r] || zeroCols[c]) {
34 matrix[r][c] = 0;
35 }
36 }
37 }
38 }
39};
40
41int main() {
42 Solution sol;
43 vector<vector<int>> matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
44 sol.setZeroes(matrix);
45 cout << "Matrix After setZeroes:" << endl;
46 for (const auto& row : matrix) {
47 for (int val : row) cout << val << " ";
48 cout << endl;
49 }
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(M * N) — We make two complete passes through the M x N matrix: one to scan for zeroes and one to update values. Total operations = 2 * (M * N) which is O(M * N).
  • Space complexity: O(M + N) — Requires auxiliary arrays zeroRows of size M and zeroCols of size N, yielding O(M + N) extra space.

3. In-Place First Row & Column Markers

Intuition

Embed the row and column markers directly inside the 0th column and 0th row of the matrix itself, using a single boolean variable for column 0.

Algorithm

  1. 1. Initialize col0 = 1 (or true).
  2. 2. Pass 1: Iterate r from 0 to M-1 and c from 0 to N-1. If c == 0 and matrix[r][0] == 0, set col0 = 0. For c > 0, if matrix[r][c] == 0, set matrix[r][0] = 0 and matrix[0][c] = 0.
  3. 3. Pass 2: Iterate inner cells from (1, 1) to (M-1, N-1). If matrix[r][0] == 0 or matrix[0][c] == 0, set matrix[r][c] = 0.
  4. 4. Pass 3: If matrix[0][0] == 0, set all cells in row 0 to 0.
  5. 5. Pass 4: If col0 == 0, set all cells in column 0 to 0.

In-Place Row 0 & Col 0 as Markers with col0 Variable

2 of 2 questions left today
Step 1 / 8
Trace timeline13% explored
InputINPUT nums = [1, 1, 1, 1, 0, 1, 1, 1, 1]
Current operationSTEP 1 OF 8
Phase 1 — col0 = 1 Begin scan: Step 1: Use the matrix's own first row and column as marker storage
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
↑ col0=1
1
1
r1
1
0
1
r2
1
1
1
Variables at this step
col0
1
Approach
O(1) Memory In-Place
Check / comparison
Instead of extra arrays, use matrix[0][..] and matrix[..][0] as markers. col0 tracks column 0.
Decision / next transition
col0 = 1. Begin scan.
Why this step matters

Phase 1 — col0 = 1 Begin scan: Step 1: Use the matrix's own first row and column as marker storage! Variable col0 = 1 tracks whether column 0 itself had a zero.

Step 1 / 8
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 void setZeroes(vector<vector<int>>& matrix) {
17 int m = matrix.size();
18 int n = matrix[0].size();
19 int col0 = 1;
20
21 for (int r = 0; r < m; ++r) {
22 if (matrix[r][0] == 0) col0 = 0;
23 for (int c = 1; c < n; ++c) {
24 if (matrix[r][c] == 0) {
25 matrix[r][0] = 0;
26 matrix[0][c] = 0;
27 }
28 }
29 }
30
31 for (int r = 1; r < m; ++r) {
32 for (int c = 1; c < n; ++c) {
33 if (matrix[r][0] == 0 || matrix[0][c] == 0) {
34 matrix[r][c] = 0;
35 }
36 }
37 }
38
39 if (matrix[0][0] == 0) {
40 for (int c = 0; c < n; ++c) matrix[0][c] = 0;
41 }
42 if (col0 == 0) {
43 for (int r = 0; r < m; ++r) matrix[r][0] = 0;
44 }
45 }
46};
47
48int main() {
49 Solution sol;
50 vector<vector<int>> matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
51 sol.setZeroes(matrix);
52 cout << "Matrix After setZeroes:" << endl;
53 for (const auto& row : matrix) {
54 for (int val : row) cout << val << " ";
55 cout << endl;
56 }
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(M * N) — We perform two complete matrix traversals and two boundary sweeps. Total operations are O(M * N) with optimal constant factor and excellent CPU cache locality.
  • Space complexity: O(1) — Only uses a single integer/boolean variable (col0) for state tracking. Auxiliary space is strictly O(1).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.1. Full Matrix Copy (Brute Force)O(M * N)O(M * N)Make a clone of the matrix to reference original zeroes while modifying.Allocates full auxiliary M x N buffer.
2.2. Row & Column Marker Arrays (Better)O(M * N)O(M + N)Track zero rows in row[M] and zero columns in col[N], then apply in pass 2.Still requires O(M + N) extra memory.
3.3. First Row & Col as Markers (Optimal)OptimalO(M * N)O(1) auxiliaryEmbed the marker arrays directly into matrix[r][0] and matrix[0][c].Optimal asymptotic runtime and space bounds.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Overwriting cells to zero immediately during the first pass: Corrupts untouched cells with fake zeroes that cascade across the entire grid.

Pitfall 2:

Forgetting to separate column 0 from row 0 at cell (0, 0): Overwriting matrix[0][0] zeroes out both row 0 and column 0 prematurely.

Pitfall 3:

Updating row 0 or column 0 before inner cells (1..m-1, 1..n-1): Destroys the marker flags before the inner cells can read them.

Crucial Edge Cases to Validate:

  • Grid with only 1 row or 1 column: col0 logic handles single-dimension borders cleanly.
  • Matrix with no zeroes: Leaves all elements intact in O(M * N) time without unnecessary writes.
  • Matrix where all elements are zero: Safely zeroes every cell without infinite loops.
  • First row or first column already containing zeroes: Handled cleanly by pass 3 and pass 4.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always clarify the space complexity requirement first. State the O(M+N) approach as a strong baseline, then optimize to O(1).
  2. Draw a 3x3 matrix on the whiteboard and explain why cell (0, 0) needs a separate col0 flag.
  3. Explain the iteration order: Scan markers first, update inner cells second, and update border rows/cols last.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for undefined?

2.Why is the brute force approach suboptimal for large inputs in undefined?

3.Which data structure or technique enables the optimal solution for undefined?

Back to DSA Sheet