Set Matrix Zeroes In Place in DSA Python - Time & Space Complexity

Time Complexity: Set Matrix Zeroes In Place

O(n x m)

Understanding Time Complexity

We want to know how the time to set zeroes in a matrix grows as the matrix size increases.

How does the number of steps change when the matrix gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    col_zero = False

    for r in range(rows):
        if matrix[r][0] == 0:
            col_zero = True
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = 0
                matrix[0][c] = 0

    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0

    if matrix[0][0] == 0:
        for c in range(cols):
            matrix[0][c] = 0

    if col_zero:
        for r in range(rows):
            matrix[r][0] = 0

This code sets entire rows and columns to zero if any element in them is zero, using the first row and column as markers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops scanning rows and columns of the matrix.
• How many times: Each element is checked or updated a few times, roughly proportional to the total number of elements (rows x columns).

How Execution Grows With Input

As the matrix size grows, the number of steps grows roughly with the number of elements.

Input Size (n x m)	Approx. Operations
10 x 10 = 100	About 300 to 400 steps
100 x 100 = 10,000	About 30,000 to 40,000 steps
1000 x 1000 = 1,000,000	About 3,000,000 to 4,000,000 steps

Pattern observation: The steps grow roughly in direct proportion to the number of elements, so doubling rows and columns quadruples the work.

Final Time Complexity

Time Complexity: O(n x m)

This means the time grows proportionally to the total number of elements in the matrix.

Common Mistake

[X] Wrong: "Since we only mark zeros in the first row and column, the time complexity is less than scanning the whole matrix twice."

[OK] Correct: We still scan almost every element multiple times to mark and then update, so the total steps scale with the entire matrix size.

Interview Connect

Understanding this helps you explain how to efficiently update large grids without extra space, a common real-world problem.

Self-Check

"What if we used extra space to store zero positions instead of marking in place? How would the time complexity change?"