Search
⌘K
PricingBecome a Coach
Search
⌘K
Get Premium
Matrices

Set Matrix Zeroes

medium
DESCRIPTION (inspired by Leetcode.com)

Write a function to modify an m x n integer matrix matrix directly, such that if any element in the matrix is 0, its entire corresponding row and column are set to 0. This transformation should be done in place, without using any additional data structures for storage.

Input:

matrix = [
    [0,2,3],
    [4,5,6],
    [7,8,9]
]

Output:

[
    [0,0,0],
    [0,5,6],
    [0,8,9]
]

Explanation: Since the element at the first row and first column is 0, set all elements in the first row and first column to 0.

Understanding the Problem

The naive approach would use O(m + n) extra space by storing which rows and columns need to be zeroed in separate sets. But we can do better by using the matrix itself as storage.
111101111→101000101InputOutput

Use the Matrix Itself!

Instead of extra arrays, we can use the first row and first column as markers. When we find a zero at [i][j], we mark:
  • matrix[i][0] = 0 → "row i needs to be zeroed"
  • matrix[0][j] = 0 → "column j needs to be zeroed"
col 0col 1col 2row 0row 1row 2First row/column = markersmatrix[i][0] = 0 means"zero out row i"matrix[0][j] = 0 means"zero out column j"
But there's a catch! If we modify the first row/column while scanning, we'll lose information about whether they originally had zeros. So we save that first.

Walkthrough

Let's trace through matrix = [[1,1,1],[1,0,1],[1,1,1]]:

Step 1: Save first row/column state

Check if the first row or column originally contains any zeros. Save in boolean flags.
111101111Step 1:Check highlighted cellsfirstRowZero = falsefirstColZero = false(no zeros in first row/col)

Step 2: Mark zeros using first row/column

Scan the inner matrix [1:][1:]. When we find a zero, mark the corresponding first row and first column cells.
101001111Step 2:Found 0 at [1][1]→ Set matrix[1][0] = 0→ Set matrix[0][1] = 0(markers for row 1 & col 1)

Step 3: Zero the inner matrix

Use the markers to zero out cells. If matrix[i][0] == 0 or matrix[0][j] == 0, set matrix[i][j] = 0.
101000101Step 3:Zero based on markers:Row 1: all zerosCol 1: all zeros(check matrix[i][0] & matrix[0][j])

Step 4: Handle first row/column

If our saved flags indicate the first row/column originally had zeros, zero them now.
101000101Step 4:firstRowZero = falsefirstColZero = false→ No changes needed✓ Done!
The order is crucial: we must save the first row/column state before using them as markers, and zero them last so we don't corrupt the markers we're reading.

Solution

|
2d-list of integers
Visualization
def setZeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][j] == 0 for j in range(cols))
    first_col_zero = any(matrix[i][0] == 0 for i in range(rows))
    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    if first_row_zero:
        for j in range(cols):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(rows):
            matrix[i][0] = 0
    return matrix
111101111firstRowZero = falsefirstColZero = false

Set Matrix Zeroes - O(1) space solution

0 / 15

Test Your Knowledge

Login to take the complexity quiz and track your progress

Complexity Analysis

Time Complexity: O(m × n) We make a constant number of passes through the matrix: once to check first row/column, once to mark, once to zero inner cells, and potentially once each for first row/column.

Space Complexity: O(1) We only use two boolean variables. The first row and column of the matrix itself serve as our markers, requiring no additional space proportional to input size.

Mark as read

Your account is free and you can post anonymously if you choose.

The best mocks on the market.

Now up to 15% off

Learn More
Reading Progress

On This Page

Understanding the Problem

Use the Matrix Itself!

Walkthrough

Step 1: Save first row/column state

Step 2: Mark zeros using first row/column

Step 3: Zero the inner matrix

Step 4: Handle first row/column

Solution

Questions
Meta SWE Interview QuestionsAmazon SWE Interview QuestionsGoogle SWE Interview QuestionsOpenAI SWE Interview QuestionsEngineering Manager (EM) Interview Questions
Learn
Learn System DesignLearn DSALearn BehavioralLearn ML System DesignLearn Low Level DesignGuided Practice
Links
FAQPricingGift Mock InterviewsGift PremiumBecome a CoachOur CoachesHello Interview Premium
Legal
Terms and ConditionsPrivacy Policy
Contact
About UsProduct Support

7511 Greenwood Ave North Unit #4238 Seattle WA 98103

© 2026 Optick Labs Inc. All rights reserved.