Search in 2D Matrix in DSA Go - Time & Space Complexity

Time Complexity: Search in 2D Matrix

O(rows x cols)

Understanding Time Complexity

We want to understand how long it takes to find a number in a 2D matrix.

How does the search time grow as the matrix gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func searchMatrix(matrix [][]int, target int) bool {
    rows := len(matrix)
    cols := len(matrix[0])
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if matrix[i][j] == target {
                return true
            }
        }
    }
    return false
}

This code checks every element in the matrix until it finds the target or finishes checking all.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• 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 size grows, the number of checks grows with the total number of elements.

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

Pattern observation: The operations grow proportionally to the total number of elements in the matrix.

Final Time Complexity

Time Complexity: O(rows x cols)

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

Common Mistake

[X] Wrong: "Since the matrix is sorted, searching is always very fast like O(log n)."

[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 real problems.

Self-Check

"What if we use binary search on each row instead of checking every element? How would the time complexity change?"