Medium — Array | Hash Table | Matrix

The Problem

Given an m x n matrix, if an element is 0, set its entire row and column to 0. The modification must be done in-place.

Approach

First pass through the matrix to identify and store all rows and columns that contain zeros using sets. Second pass through the matrix to set elements to zero if their row or column was marked in the first pass.

Time: O(m * n) · Space: O(m + n)

Code

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        

        rows, cols = len(matrix), len(matrix[0])
        zero_rows, zero_cols = set(), set()

        # Mark rows and columns that need to be set to zero
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == 0:
                    zero_rows.add(i)
                    zero_cols.add(j)

        # Set elements to zero based on marked rows and columns
        for i in range(rows):
            for j in range(cols):
                if i in zero_rows or j in zero_cols:
                    matrix[i][j] = 0

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment