Set Matrix Zeroes - Video Solutions

Problem Overview: Given an m × n matrix, if any element is 0, you must set its entire row and column to 0. The tricky part is doing this without accidentally spreading zeros while scanning the matrix.

Approach 1: Using Additional Space (O(mn) time, O(m+n) space)

This approach tracks which rows and columns must be zeroed using extra data structures. First iterate through the matrix and record indices of rows and columns containing a zero. A set or boolean array works well for this. During a second pass, check whether row i or column j was marked and update matrix[i][j] to zero accordingly. The key idea is separating the detection phase from the update phase so newly written zeros don’t affect the scan. This solution is easy to reason about and commonly used when memory constraints are not strict. The full scan gives O(mn) time complexity and the extra row/column markers require O(m+n) space.

This method relies heavily on sequential traversal of the matrix and efficient membership checks. Using hash-based sets for row and column indices keeps lookup operations constant time. The logic is straightforward and makes a good baseline solution when solving array and grid-based interview problems.

Approach 2: Using the Matrix Itself (O(mn) time, O(1) space)

The optimal solution removes the need for extra storage by using the first row and first column of the matrix as markers. During the first pass, when a zero appears at matrix[i][j], mark the row and column by setting matrix[i][0] and matrix[0][j] to zero. Because the first row and column are reused as markers, track whether they originally contained zeros using two boolean flags. In a second pass, iterate through the inner matrix and zero out cells based on the markers stored in the first row and column. Finally update the first row and column if their flags were set.

The key insight is that the matrix already provides enough space to store row/column markers. This reduces the auxiliary memory from O(m+n) to O(1). The algorithm still performs two linear scans of the grid, so the runtime remains O(mn). Problems like this frequently appear in interviews to test whether you can reuse existing memory instead of allocating extra structures such as a hash table.

Recommended for interviews: Interviewers usually expect the in-place marker approach. Starting with the extra-space solution shows clear thinking and correctness. Improving it to reuse the first row and column demonstrates stronger optimization skills and awareness of space complexity constraints.