Skip to main content
CodeEasy v0.1

Set Matrix Zeroes

Medium Subject: Math & Geometry
Time Complexity
O(M * N)
Space Complexity
O(1)

Problem Description

Problem Statement

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. You must do it in place.

Example 1:

  • Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
  • Output: [[1,0,1],[0,0,0],[1,0,1]]

Optimal Solution

Python

Approach: In-Place Hashing with First Row/Col

Use the first row and first column as flags to mark which rows and columns need to be zeroed. We use two extra variables to track if the first row and first column themselves need to be zeroed. We do two passes: one to mark, and one to update.

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        first_row = first_col = False

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    if i == 0: first_row = True
                    if j == 0: first_col = True
                    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:
            for j in range(n): matrix[0][j] = 0
        if first_col:
            for i in range(m): matrix[i][0] = 0