Start learning free

LESSON 336 OF 673 · MATRIX

Set Matrix Zeroes in Python: Mark First, Clear Later

Practice O(m*n) Read the full explanation

You get a grid of integers, matrix, with m rows and n columns.

Wherever a cell is 0, set its whole row and its whole column to 0. Change matrix in place and return nothing.

Only the zeros that are there at the start count. A cell you turn into 0 doesn't clear anything more.

The grid is a list of rows. Each row is a list of integers. Rows are counted from 0 at the top, columns from 0 at the left.

 

Example 1:

Input: matrix = [
  [4, 0, 6],
  [7, 8, 9]
]
Output: [
  [0, 0, 0],
  [7, 0, 9]
]
Explanation: The 0 is in row 0, column 1.
It clears row 0 and column 1.
The 7 and the 9 stay.

Example 2:

Input: matrix = [
  [2, 5, 8],
  [0, 3, 1],
  [6, 4, 0]
]
Output: [
  [0, 5, 0],
  [0, 0, 0],
  [0, 0, 0]
]
Explanation: Two cells are 0 at the start.
The 0 in row 1, column 0 clears row 1 and column 0.
The 0 in row 2, column 2 clears row 2 and column 2.
The 5 stays. Row 0 and column 1 had no 0 at the start.
The new zeros in row 0 don't count.

Example 3:

Input: matrix = [
  [7, 2, 9, 3]
]
Output: [
  [7, 2, 9, 3]
]
Explanation: There is no 0. Nothing changes.

 

Constraints:

  • 1 to 500 rows.
  • 1 to 500 columns.
  • All rows have the same length.
  • Each value fits in a 32-bit signed integer: -231 to 231 - 1.

Note:

Your algorithm should run in O(m * n) time and use O(m + n) extra space.

Follow-up: can you do it with O(1) extra space? The first row and the first column of matrix can hold the marks for the other rows and columns.

STEP 1 OF 9
    Ctrl + Enter to check

    PYTHON · MATRIX

    Set Matrix Zeroes in Python, explained

    Problem overview

    The method setZeroes receives an m x n matrix of integers, a list of m rows with n numbers each. Wherever an element is 0, its entire row and its entire column must become 0. The change happens in place, and the method returns nothing.

    Only the zeros present at the start count. A cell that becomes 0 during the process does not clear its own row and column. In [[1, 1, 1], [1, 0, 1], [1, 1, 1]] the only zero is in row 1 and column 1, so the middle row and the middle column become 0 and the result is [[1, 0, 1], [0, 0, 0], [1, 0, 1]].

    The required time is O(m * n) and the extra space is O(m + n). The lesson mentions a follow-up with O(1) extra space, where the first row and column store the marks.

    Approach: remember now, clear later

    The tempting solution scans the matrix and, on meeting a zero, zeroes its row and column right away. That fails because the new zeros look exactly like the original ones. When the scan reaches them, it clears more rows and columns than it should. On [[1, 0, 1], [1, 1, 1], [1, 1, 1]], this approach clears the whole matrix and returns all zeros, where the correct answer is [[0, 0, 0], [1, 0, 1], [1, 0, 1]].

    The fix is to separate looking from changing, using two passes:

    1. The first pass only reads. It records which rows and which columns contain a zero, in two lists of booleans.
    2. The second pass writes. A cell becomes 0 if its row or its column was marked.

    The marks cost m + n booleans, which is where the O(m + n) space comes from. Marking a row twice, because it holds two zeros, changes nothing, so no care is needed for repeated zeros.

    On the third example, [[0, 2, 3, 4], [5, 0, 7, 8], [9, 10, 11, 12]], the zeros are at row 0 column 0 and row 1 column 1. The marks therefore cover rows 0 and 1 and columns 0 and 1. The second pass clears those, and 11 and 12 are the only cells outside all four, so the result is [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 11, 12]].

    Step by step

    1. Store the dimensions: m is len(matrix), the number of rows, and n is len(matrix[0]). Every row has the same length, so the first row gives the number of columns.
    2. Create the marks: zeroRow is [False] * m and zeroCol is [False] * n. zeroRow[i] says whether row i has a zero, and zeroCol[j] does the same for column j.
    3. Loop over every row with i in range(m). This first pass changes nothing.
    4. Loop over every column of that row with j in range(n), so each cell is reached once.
    5. Test the cell: matrix[i][j] == 0.
    6. Mark its row and column by setting zeroRow[i] and zeroCol[j] to True.
    7. Start the second pass with a new loop over range(m), outside the first pair of loops. Every zero has been recorded, so cells can change without losing information.
    8. Loop over the columns again with j in range(n).
    9. Clear the cell if zeroRow[i] or zeroCol[j] is true by setting matrix[i][j] to 0.

    The solution in Python

    class Solution:
        def setZeroes(self, matrix: List[List[int]]) -> None:
            m = len(matrix)
            n = len(matrix[0])
            zeroRow = [False] * m
            zeroCol = [False] * n
            for i in range(m):
                for j in range(n):
                    if matrix[i][j] == 0:
                        zeroRow[i] = True
                        zeroCol[j] = True
            for i in range(m):
                for j in range(n):
                    if zeroRow[i] or zeroCol[j]:
                        matrix[i][j] = 0
    

    The Python details that matter here:

    • [False] * m is safe for booleans. Assigning zeroRow[i] = True replaces one slot and leaves the others alone.
    • The method returns None. Calling setZeroes(matrix) changes the caller's list in place, and the result is read from matrix afterwards.
    • Only exact zeros count. The test matrix[i][j] == 0 matches the integer 0 and nothing else. Negative numbers and very large numbers are ordinary cells, and Python integers have no overflow.
    • or short-circuits. When the row is already marked, the column mark is not even looked at, which is fine because either one is enough.

    Complexity

    Time: O(m * n). The method visits every cell twice, once per pass, and each visit costs constant time.

    Space: O(m + n). zeroRow holds m booleans and zeroCol holds n. The matrix itself is changed in place and never copied.

    The O(1) follow-up stores the same information inside the first row and the first column of matrix. Those cells then have two jobs, so it needs two extra booleans to remember whether the first row and the first column held a zero of their own.

    Edge cases and common mistakes

    • Clearing while scanning. Zeroing a row and column the moment a zero is found makes new zeros trigger more clearing, as shown above. The two-pass structure exists to prevent it.
    • No zeros. The marks stay False and the matrix is unchanged. A single cell such as [[5]] comes back as [[5]].
    • A single row or column. [[0, 1]] becomes [[0, 0]], and [[1, 2, 3]] stays as it is.
    • Zeros that share a line. In [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]] both zeros are in row 0. Row 0 is marked twice, which is harmless, and columns 0 and 3 are marked once each.
    • Mixing up the lists. zeroRow has m entries and is indexed by i. zeroCol has n entries and is indexed by j. Swapping them marks the wrong lines on a non-square matrix and can raise an IndexError.

    Testing

    • [[1, 1, 1], [1, 0, 1], [1, 1, 1]] becomes [[1, 0, 1], [0, 0, 0], [1, 0, 1]].
    • [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]] becomes [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]].
    • [[0, 2, 3, 4], [5, 0, 7, 8], [9, 10, 11, 12]] becomes [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 11, 12]].
    • [[1, 0, 1], [1, 1, 1], [1, 1, 1]] becomes [[0, 0, 0], [1, 0, 1], [1, 0, 1]].
    • [[0, 1]] becomes [[0, 0]].
    Keep going with Python650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free