DSA interview question

Set Matrix Zeroes

Medium · Algorithms · Topics: array, matrix, hash set

The problem

A spreadsheet tool has a "zero out" rule: if any cell in a table is 0, its entire row and entire column must become 0. The trap is that zeroing as you go creates new zeros that then wrongly spread further. The simple fix uses two extra arrays to remember which rows and columns contain an original zero. The interview version asks for O(1) extra space: use the first row and first column of the matrix itself as those marker arrays, with one extra flag for the first column.

Example: [[1, 1, 1], [1, 0, 1], [1, 1, 1]] → [[1, 0, 1], [0, 0, 0], [1, 0, 1]].

Function signature

void setZeroes(vector<vector<int>>& m);  // in place, O(1) extra space

Test cases

Input `m`	Output	Explanation
`[[1,1,1],[1,0,1],[1,1,1]]`	`[[1,0,1],[0,0,0],[1,0,1]]`	Middle row and column
`[[0,1,2,0],[3,4,5,2],[1,3,1,5]]`	`[[0,0,0,0],[0,4,5,0],[0,3,1,0]]`	Zeros in the first row itself
`[[1]]`	`[[1]]`
`[[0]]`	`[[0]]`
`[[1,0]]`	`[[0,0]]`	A single row
`[[1],[0]]`	`[[0],[0]]`	A single column

(Confirm: only zeros present in the original matrix trigger clearing; in place with O(1) extra space.)

How interviewers phrase it

"If an element is 0, set its entire row and column to 0, in place" (LeetCode 73).
"Can you do it with constant extra space?"

Clarifying questions to ask

Should only the original zeros trigger clearing? (Yes, and that's the main trap.)
Is O(m + n) extra space acceptable, or must it be O(1)?
Can the matrix have a single row or column?

Follow-ups to expect

"What's wrong with zeroing immediately when you see a 0?"
"What's the O(m + n) solution?"
"How does the O(1) version work?"
"Why process the matrix from the bottom-right when clearing?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview