Spiral Matrix Traversal in DSA C - Time & Space Complexity

Time Complexity: Spiral Matrix Traversal

O(rows * cols)

Understanding Time Complexity

We want to understand how the time needed to traverse a matrix in a spiral 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.

void spiralTraversal(int matrix[][N], int rows, int cols) {
    int top = 0, bottom = rows - 1;
    int left = 0, right = cols - 1;
    while (top <= bottom && left <= right) {
        for (int i = left; i <= right; i++) printf("%d ", matrix[top][i]);
        top++;
        for (int i = top; i <= bottom; i++) printf("%d ", matrix[i][right]);
        right--;
        if (top <= bottom) {
            for (int i = right; i >= left; i--) printf("%d ", matrix[bottom][i]);
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) printf("%d ", matrix[i][left]);
            left++;
        }
    }
}
    

This code prints all elements of a matrix in a spiral order starting from the top-left corner.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each element of the matrix exactly once.
• How many times: Each element is printed once during the spiral traversal loops.

How Execution Grows With Input

As the matrix size grows, the number of elements to visit grows too.

Input Size (n x n)	Approx. Operations (elements visited)
10 x 10	100
100 x 100	10,000
1000 x 1000	1,000,000

Pattern observation: The operations grow proportionally to the total number of elements, which is the square of the matrix dimension.

Final Time Complexity

Time Complexity: O(rows * cols)

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

Common Mistake

[X] Wrong: "Because there are nested loops, the time complexity must be O(n²) regardless of matrix shape."

[OK] Correct: The loops do not multiply the work repeatedly; each element is visited once, so the total work is proportional to the number of elements, not squared again.

Interview Connect

Understanding how to analyze traversal of 2D structures like matrices is a key skill. It shows you can reason about loops and data size clearly, which helps in many coding problems.

Self-Check

"What if the matrix was not rectangular but jagged (rows of different lengths)? How would the time complexity change?"