Time Complexity: Set Matrix Zeroes In Place

O(m x n)

Understanding Time Complexity

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

Specifically, how many steps does it take to update the matrix in place?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int rows = matrixSize;
    int cols = *matrixColSize;
    int firstRowZero = 0;
    int firstColZero = 0;

    for (int i = 0; i < rows; i++) {
        if (matrix[i][0] == 0) firstColZero = 1;
    }
    for (int j = 0; j < cols; j++) {
        if (matrix[0][j] == 0) firstRowZero = 1;
    }

    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }

    if (firstColZero) {
        for (int i = 0; i < rows; i++) matrix[i][0] = 0;
    }
    if (firstRowZero) {
        for (int j = 0; j < cols; j++) matrix[0][j] = 0;
    }
}

This code sets entire rows and columns to zero if any element in them is zero, modifying the matrix in place.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

Primary operation: Nested loops scanning the matrix elements twice.
How many times: Each nested loop runs roughly rows x cols times.

How Execution Grows With Input

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

Input Size (rows x cols)	Approx. Operations
10 x 10 = 100	About 400 (4 passes over matrix)
100 x 100 = 10,000	About 40,000
1000 x 1000 = 1,000,000	About 4,000,000

Pattern observation: Operations grow roughly proportional to the total number of elements, multiplied by a small constant.

Final Time Complexity

Time Complexity: O(m x n)

This means the time grows linearly with the number of elements in the matrix.

Common Mistake

[X] Wrong: "The time complexity is O((m x n)²) because of nested loops inside nested loops."

[OK] Correct: The nested loops run sequentially, not nested inside each other repeatedly; each element is visited a fixed number of times, not multiplied repeatedly.

Interview Connect

Understanding how to analyze matrix operations helps you solve many real problems efficiently and shows you can reason about code performance clearly.

Self-Check

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

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

Practice

Solution

Step 1: Understand the problem requirement

Step 2: Note the constraint of in-place modification

Final Answer:

Quick Check:

Solution

Step 1: Check correct 2D array declaration syntax in C

Step 2: Validate each option

Final Answer:

Quick Check:

Solution

Step 1: Identify zero positions in original matrix

Step 2: Set entire row 0 and column 1 to zero

Final Answer:

Quick Check:

Solution

Step 1: Analyze immediate zeroing inside nested loops

Step 2: Understand cascading zeroing problem

Final Answer:

Quick Check:

Solution

Step 1: Identify zero positions

Step 2: Determine first row and first column zero flags

Step 3: Mark zeros using first row and column (inner matrix)

Step 4: Zero inner matrix using marks

Step 5: Apply flags to borders

Final Answer:

Quick Check:

Ready to prove it?