Set Matrix Zeroes: LeetCode 73 Solution Explained

Set Matrix Zeroes (#73) is one of the best problems for learning a technique that shows up everywhere in matrix and array algorithms: using the data structure itself as storage. Instead of allocating extra space to track which rows and columns need to be zeroed, you repurpose the first row and first column as marker arrays.

This problem is a favorite at Amazon, Microsoft, and Bloomberg because it tests whether you can move past the obvious O(m+n) space solution and think about in-place optimization. The brute-force approach is straightforward, but the O(1) space solution requires careful ordering of operations — exactly the kind of detail interviewers want to see you handle.

In this walkthrough, you will understand both approaches, see why the order of operations matters in the constant-space version, and learn a pattern that applies to many other in-place algorithms.

You are given an m x n integer matrix. If any element is 0, you must set its entire row and its entire column to 0. The catch: you must do it in-place, modifying the original matrix without returning a new one.

At first glance, this sounds simple — find the zeroes and zero out their rows and columns. But if you start zeroing immediately, the new zeroes you create will trigger even more zeroing in a cascade that corrupts your result. You need a way to remember which cells were originally zero before you start modifying anything.

The constraints are generous: the matrix can be up to 200 x 200, so even an O(m * n * (m + n)) brute-force solution would pass. But the real interview question is whether you can do it in O(1) auxiliary space — and that is where the elegance lies.

The most intuitive approach is to scan the matrix once and record which rows and columns contain at least one zero. You can use two sets — one for zero-rows and one for zero-columns. Then make a second pass and set matrix[i][j] to 0 whenever row i or column j is in the respective set.

This runs in O(m * n) time with O(m + n) space for the two sets. It is clean, easy to implement, and perfectly correct. In a real interview, starting here is a smart move — it shows you understand the problem before optimizing.

The code is straightforward: iterate through every cell, add row and column indices to their respective sets when you find a zero, then iterate again and zero out any cell whose row or column appears in the sets.

The key insight for the O(1) space solution is that you do not need separate sets at all. The first row and first column of the matrix can serve as your marker arrays. When you find a zero at matrix[i][j], you mark matrix[i][0] = 0 (marking row i) and matrix[0][j] = 0 (marking column j).

There is one subtlety: the cell matrix[0][0] would be used to mark both the first row and the first column, which creates a conflict. The solution is to use matrix[0][0] for the first column only, and a separate boolean variable to track whether the first row itself needs to be zeroed.

The algorithm has four phases. First, scan the entire matrix and mark the first row and first column as described. Second, use the markers to zero out all interior cells (rows 1 to m-1, columns 1 to n-1). Third, if matrix[0][0] is 0, zero the entire first column. Fourth, if the boolean flag is set, zero the entire first row.

This approach achieves O(m * n) time and O(1) auxiliary space — the only extra storage is a single boolean variable. It is the textbook example of using the data structure itself as scratch space.

The order of operations in the O(1) solution is critical and is the number one source of bugs. You must zero the interior cells before you zero the first row and first column. If you zero the first row or column too early, you destroy the markers that tell you which interior cells to zero.

Here is the step-by-step process. Start by checking if the first row contains any zero — store this in a boolean. Then scan rows 1 through m-1: for each zero found, set matrix[i][0] = 0 and matrix[0][j] = 0. Next, iterate through the interior (i from 1 to m-1, j from 1 to n-1) and set matrix[i][j] = 0 whenever matrix[i][0] == 0 or matrix[0][j] == 0.

After the interior is processed, check matrix[0][0]. If it is 0, zero the entire first column (j = 0 for all rows). Finally, if your boolean flag indicates the first row had a zero, zero the entire first row. This ordering guarantees that markers are consumed before they are overwritten.

Several edge cases deserve attention. If the matrix has no zeroes at all, nothing should change — your markers will all remain non-zero and the matrix stays untouched. If every cell is zero, the entire matrix remains zero, which is trivially handled.

A zero in the first row or first column is the trickiest case. Since these are your marker arrays, you must handle them with the separate boolean (for the first row) and matrix[0][0] (for the first column). Forgetting this distinction is the most common bug.

Single-row or single-column matrices are valid inputs. For a single row, any zero means the entire row becomes zero. For a single column, any zero means the entire column becomes zero. Your code should handle these naturally without special-casing, but verify with a quick test.

The core lesson from LeetCode 73 is the "use the data structure itself as storage" pattern. Instead of allocating extra memory to track state, you repurpose existing cells that you can reconstruct later. This same idea powers in-place algorithms like cycle sort, Floyd's duplicate detection, and first missing positive (#41).

In interviews, this problem tests your ability to optimize space without sacrificing correctness. The jump from O(m+n) to O(1) space is not about clever tricks — it is about recognizing that the information you need to store (which rows and columns to zero) fits perfectly into space the matrix already provides.

If you want to drill this pattern until it becomes second nature, YeetCode flashcards let you review Set Matrix Zeroes and related in-place matrix problems with spaced repetition. Recognizing when you can eliminate auxiliary storage is a skill that transfers to dozens of other problems.