Search in 2D Matrix in DSA C++ - Time & Space Complexity

Time Complexity: Search in 2D Matrix

O(m x n)

Understanding Time Complexity

We want to understand how the time needed to find a number in a 2D matrix changes as the matrix size grows.

Specifically, how does searching through rows and columns affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == target) {
                return true;
            }
        }
    }
    return false;
}
    

This code checks every element in the matrix one by one to find the target number.

Identify Repeating Operations

• Primary operation: Checking each element in the matrix.
• How many times: The outer loop runs once per row, and the inner loop runs once per column, so total checks = rows x columns.

How Execution Grows With Input

As the matrix gets bigger, the number of checks grows by multiplying rows and columns.

Input Size (rows x cols)	Approx. Operations
10 x 10	100 checks
100 x 100	10,000 checks
1000 x 1000	1,000,000 checks

Pattern observation: Doubling rows and columns causes the total work to grow by the square of the size increase.

Final Time Complexity

Time Complexity: O(m x n)

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

Common Mistake

[X] Wrong: "Since the matrix is sorted, searching is always fast like binary search."

[OK] Correct: This code checks every element without using the sorted order, so it still takes time proportional to all elements.

Interview Connect

Understanding how nested loops affect time helps you explain and improve search methods in matrices during interviews.

Self-Check

"What if we use a search method that starts from the top-right corner and moves left or down based on comparisons? How would the time complexity change?"