MediumArrayHash TableMatrixUpdated Sep 2026

73. Set Matrix Zeroes

Asked at Oracle

Difficulty

Medium

Time

O(m * n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You are given an m x n integer matrix. Whenever a cell holds the value 0, the whole row and the whole column that contain that cell must become 0 as well.

All of this must happen in place — you change the given matrix itself and return nothing. The tricky part: the zeros you write can look like original zeros, so you must decide which rows and columns to clear based on the matrix as it was at the start, not as it changes.

A simple fix is to remember the zero rows and zero columns in extra sets. That costs O(m + n) extra space. The challenge is to do it with O(1) extra space, by reusing the first row and first column of the matrix as your bookkeeping area.

One zero clears a whole row and column

before012012111101111The red cell is the only zero in the input.after012012101000101Row 1 and column 1 are now zero; the other four cellskeep their values.
The single zero at row 1, column 1 forces row 1 and column 1 to become zeros, while the corners stay as they were.

Constraints

  • ●m == matrix.length
  • ●n == matrix[0].length
  • ●1 <= m, n <= 200
  • ●-2^31 <= matrix[i][j] <= 2^31 - 1

Examples

Example 1
Inputmatrix = [[1,1,1],[1,0,1],[1,1,1]]
Output[[1,0,1],[0,0,0],[1,1,1]]
WhyThe only zero sits at row 1, column 1. So row 1 becomes all zeros and column 1 becomes all zeros. The four corner cells are untouched because they are in neither that row nor that column.
Example 2
Inputmatrix = [[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]]
WhyOriginal zeros are at (0,0) and (0,3). Row 0 is cleared, and columns 0 and 3 are cleared. Cell (1,1) keeps 4 and (2,2) keeps 1 because their row and column had no original zero.

Asked At

1 companies
CompanyDifficulty
OracleMediumView all Oracle questions →

How to Think About It

1

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.

2

Use the first row and first column as markers: store whether each row/col should be zeroed.

3

Handle the first row and first column separately since they serve as the marker storage.

4

Use a single boolean flag for whether the first row needs zeroing, since matrix[0][0] is shared.

5

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.

Use row 0 and column 0 as marker storage

mark zeros012012111101111Find a zero at (1,1) and write a marker intomatrix[1][0] and matrix[0][1].markers set012012101001111The blue cells are markers: column 1 and row 1 needclearing.clear inner012012101000101For each inner cell, zero it if its row marker orcolumn marker is zero.firstRowZero = any zero in row 0firstColZero = any zero in column 0matrix[i][0] = 0 marks row imatrix[0][j] = 0 marks column jclear row 0 / column 0 last
Instead of extra arrays, the first row and first column record which rows and columns must be cleared.
ComplexityTime O(m * n)Space O(1)The matrix is scanned a constant number of times, and the first row plus first column are reused as markers instead of allocating new arrays.

What Trips People Up in Real Interviews

1

Clarify whether the input matrix can be modified in place or if extra space is allowed.

2

Ask about the first row and first column edge case early — they overlap at matrix[0][0].

3

Walk through the marker logic step by step before writing code.

4

Mention the O(m+n) space solution first, then optimize to O(1) if the interviewer pushes.

5

Test with a matrix that has zeros in the first row, first column, and interior.

Solution Code

O(m * n) time
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] = 0

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(m * n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.