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

Time Complexity: Search in 2D Matrix

O(m x n)

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 when the matrix gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function searchMatrix(matrix: number[][], target: number): boolean {
  for (let row = 0; row < matrix.length; row++) {
    for (let col = 0; col < matrix[row].length; col++) {
      if (matrix[row][col] === target) {
        return true;
      }
    }
  }
  return false;
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each element in the matrix.
• How many times: For each row, it checks every column element, so total checks = number of rows x number of 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(m x n)

This means the time to search grows directly with the number of rows (m) times the number of columns (n).

Common Mistake

[X] Wrong: "The search will always be fast because we stop when we find the target."

[OK] Correct: In the worst case, the target might be at the very end or not present, so the code checks every element, making the time grow with the whole matrix size.

Interview Connect

Understanding this helps you explain how searching in a grid works and why sometimes it takes longer when the data grows.

Self-Check

"What if the matrix rows and columns were sorted, and we used a smarter search? How would the time complexity change?"