Set Matrix Zeroes
Asked at Oracle
Problem
Given an m x n matrix, if an element is 0, set its entire row and column to 0. You must do it in place without using extra space proportional to the matrix dimensions. The solution should use O(1) additional space beyond the input.
Asked At
| Company | Difficulty | |
|---|---|---|
| Oracle | MEDIUM | View all Oracle questions → |
How to Think About It
Brute force: use a set to record which rows and columns contain zeros, then zero them out — O(m*n) time, O(m+n) space.
Use the first row and first column as markers: store whether each row/col should be zeroed.
Handle the first row and first column separately since they serve as the marker storage.
Use a single boolean flag for whether the first row needs zeroing, since matrix[0][0] is shared.
Optimal in-place: scan the matrix, mark zeros in the first row/col, then zero inner cells, then handle first row/col last — O(1) space.
Optimal Approach
First, check if the first row or first column originally contain any zeros and store this in two boolean flags. Then use the first row and first column as marker arrays: for each cell (i,j) that is zero, set matrix[i][0] = 0 and matrix[0][j] = 0. After marking, iterate through the inner matrix (excluding first row and column) and zero any cell whose row or column marker is zero. Finally, zero the first row and first column if their respective flags were set. This achieves O(1) extra space.
What Trips People Up in Real Interviews
Clarify whether the input matrix can be modified in place or if extra space is allowed.
Ask about the first row and first column edge case early — they overlap at matrix[0][0].
Walk through the marker logic step by step before writing code.
Mention the O(m+n) space solution first, then optimize to O(1) if the interviewer pushes.
Test with a matrix that has zeros in the first row, first column, and interior.
Solution Code
def set_zeroes(matrix):
if not matrix or not matrix[0]:
return
m, n = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_zero = any(matrix[i][0] == 0 for i in range(m))
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_zero:
for i in range(m):
matrix[i][0] = 0Frequently Asked Questions
What is the Set Matrix Zeroes problem?
Given an m x n matrix, if an element is 0, set its entire row and column to 0. You must do it in place without using extra space proportional to the matrix dimensions. The solution should use O(1) additional space beyond the input.
How do you solve Set Matrix Zeroes?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Set Matrix Zeroes?
Set Matrix Zeroes is asked at Oracle. It is a medium difficulty problem.
What are common mistakes on Set Matrix Zeroes?
- Clarify whether the input matrix can be modified in place or if extra space is allowed.
- Ask about the first row and first column edge case early — they overlap at matrix[0][0].
- Walk through the marker logic step by step before writing code.
- Mention the O(m+n) space solution first, then optimize to O(1) if the interviewer pushes.
- Test with a matrix that has zeros in the first row, first column, and interior.