Introduction

Traversing a two-dimensional array means visiting its elements in some order, usually row by row or column by column. The most common interview and algorithm question is what that costs in time.

In the standard case, the answer is proportional to the number of elements you touch. For an array with m rows and n columns, a full traversal takes O(m * n) time.

Why the Complexity Is O(m * n)

A 2D array with m rows and n columns contains m * n elements. If your algorithm visits each element once and does constant work per visit, the total work is:

m * n * O(1) = O(m * n)

That is the core idea. Time complexity depends on how many cells are processed, not on how many for loops appear in the source code.

Here is a simple Python example:

1matrix = [
2    [1, 2, 3],
3    [4, 5, 6],
4    [7, 8, 9],
5]
6
7for row in matrix:
8    for value in row:
9        print(value)

The nested loops do not automatically mean O(n^2) in every case. They mean the runtime is the product of the loop lengths. For a matrix with dimensions m and n, that is O(m * n).

Square Matrix Versus Rectangular Matrix

If the matrix is square, with n rows and n columns, then m = n, so O(m * n) becomes O(n^2).

That is why many examples in textbooks say traversing a matrix is O(n^2). They are assuming a square matrix. In the more general case, O(m * n) is the more accurate statement.

For example:

• a 100 x 100 matrix has 10,000 elements
• a 100 x 3 matrix has 300 elements
• both use nested loops, but the actual work differs a lot

So it is better to describe the complexity in terms of both dimensions when possible.

Different Traversal Orders, Same Asymptotic Cost

You can traverse a 2D array in many orders:

• row-major order
• column-major order
• diagonal order
• spiral order
• zigzag order

If the algorithm still visits every element exactly once, the time complexity remains O(m * n).

Here is a row-major traversal in Java:

1public class TraverseMatrix {
2    public static void main(String[] args) {
3        int[][] matrix = {
4            {1, 2, 3},
5            {4, 5, 6}
6        };
7
8        for (int i = 0; i < matrix.length; i++) {
9            for (int j = 0; j < matrix[i].length; j++) {
10                System.out.println(matrix[i][j]);
11            }
12        }
13    }
14}

Whether you print, sum, or count the elements, the asymptotic traversal cost is still tied to the number of cells visited.

When the Complexity Is Less Than Full Traversal

Not every algorithm over a 2D array touches every element. If you stop early, complexity changes.

For example, searching for a target and returning as soon as it is found may be faster in practice:

1def contains(matrix, target):
2    for row in matrix:
3        for value in row:
4            if value == target:
5                return True
6    return False

Worst-case time is still O(m * n) because the target might be absent or located at the last cell. Best-case time is O(1) if the first element matches.

That is why algorithm discussions often distinguish between worst-case, average-case, and best-case complexity.

Space Complexity of Traversal

A normal iterative traversal uses O(1) extra space, ignoring the input array itself.

1total = 0
2for row in matrix:
3    for value in row:
4        total += value

The algorithm keeps only a few variables while scanning the matrix. If you build a second matrix or recursive traversal structure, extra space can increase, but plain traversal itself is constant-space.

Common Pitfalls

One common mistake is saying “nested loops means O(n^2)” without checking whether the two loop bounds are actually the same variable. For a general 2D array, O(m * n) is the correct expression.

Another issue is forgetting that complexity depends on visited elements. If an algorithm skips parts of the matrix or exits early, the exact runtime behavior may differ from full traversal.

It is also easy to mix up time and space complexity. A full scan may be O(m * n) in time while still using only O(1) extra space.

Finally, do not confuse asymptotic complexity with cache performance. Two traversal orders can both be O(m * n) while still having different real-world speed because of memory layout.

Summary

• Fully traversing an m x n 2D array takes O(m * n) time.
• If the matrix is square, that becomes O(n^2).
• The traversal order does not change asymptotic complexity as long as every element is visited once.
• Early exit algorithms may have smaller best-case runtime, but full worst-case traversal is still O(m * n).
• Plain iterative traversal usually uses O(1) extra space.