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

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?"