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

Time Complexity: Search in 2D Matrix

O(n * m)

Understanding Time Complexity

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

Specifically, how the search time grows as the matrix gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function searchMatrix(matrix, target) {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      if (matrix[i][j] === target) {
        return true;
      }
    }
  }
  return false;
}
    

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

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 for each row, and the inner loop runs for each column in that row.

How Execution Grows With Input

As the matrix size grows, the number of checks grows with the total number of elements.

Input Size (n x m)	Approx. Operations
10 x 10	100 checks
100 x 100	10,000 checks
1000 x 1000	1,000,000 checks

Pattern observation: The operations grow roughly by the total number of elements, so doubling rows and columns quadruples work.

Final Time Complexity

Time Complexity: O(n * m)

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

Common Mistake

[X] Wrong: "Since the matrix is sorted, we can find the target in constant time."

[OK] Correct: Even if sorted, this code checks every element one by one, so it still takes time proportional to all elements in the worst case.

Interview Connect

Understanding how nested loops affect time helps you explain and improve search methods in real problems.

Self-Check

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