Search in 2D Matrix in DSA Typescript

Mental Model

We look for a number in a grid where each row and column is sorted. We move step by step to find if the number exists.

Analogy: Imagine a library where books are arranged by title from left to right and shelves are arranged by author from top to bottom. To find a book, you start at the top-right corner and move left or down depending on the title you want.

Matrix:
1  3  5  7
10 11 16 20
23 30 34 50

Start at top-right corner (7):
1  3  5  [7↑]
10 11 16 20
23 30 34 50

Dry Run Walkthrough

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3

Goal: Find if 3 exists in the matrix

Step 1: Start at top-right element (7)

1  3  5  [7↑]
10 11 16 20
23 30 34 50

Why: We start here because it helps decide whether to move left or down

Step 2: Compare 7 with target 3, since 7 > 3, move left

1  3  [5↑] 7
10 11 16 20
23 30 34 50

Why: Moving left goes to smaller numbers to find target

Step 3: Compare 5 with target 3, since 5 > 3, move left

1  [3↑] 5  7
10 11 16 20
23 30 34 50

Why: Keep moving left to smaller numbers

Step 4: Compare 3 with target 3, found target

1  [3↑] 5  7
10 11 16 20
23 30 34 50

Why: Target found, stop searching

Result:

1  [3↑] 5  7
10 11 16 20
23 30 34 50
Answer: true

Annotated Code

DSA Typescript

class MatrixSearch {
  static searchMatrix(matrix: number[][], target: number): boolean {
    if (matrix.length === 0 || matrix[0].length === 0) {
      return false;
    }
    let row = 0;
    let col = matrix[0].length - 1;

    while (row < matrix.length && col >= 0) {
      if (matrix[row][col] === target) {
        return true; // found target
      } else if (matrix[row][col] > target) {
        col--; // move left to smaller numbers
      } else {
        row++; // move down to larger numbers
      }
    }
    return false; // target not found
  }
}

// Driver code
const matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
];
const target = 3;
console.log(MatrixSearch.searchMatrix(matrix, target));

while (row < matrix.length && col >= 0) {

loop while inside matrix bounds

if (matrix[row][col] === target) {

check if current element is target

col--;

move left if current element is bigger than target

row++;

move down if current element is smaller than target

Output

true

Complexity Analysis

Time: O(m + n) because we move at most m times down and n times left in the matrix

Space: O(1) because we use only a few variables, no extra space proportional to input

vs Alternative: Compared to searching every element (O(m*n)), this approach is much faster by skipping many elements

Edge Cases

Empty matrix

Returns false immediately because no elements to search

DSA Typescript

if (matrix.length === 0 || matrix[0].length === 0) {

Target smaller than smallest element

Moves left from top-right until out of bounds, returns false

DSA Typescript

col--;

Target larger than largest element

Moves down from top-right until out of bounds, returns false

DSA Typescript

row++;

When to Use This Pattern

When you see a sorted 2D matrix and need to find a number quickly, use the top-right corner search pattern to move left or down and reduce search space efficiently.

Common Mistakes

Mistake: Starting search from top-left or bottom-left corner without adjusting moves properly
Fix: Always start from top-right corner and move left or down based on comparison

Mistake: Not checking matrix bounds before accessing elements
Fix: Use while loop conditions to ensure row and col are within matrix limits

Summary

Searches a sorted 2D matrix for a target number efficiently.

Use when matrix rows and columns are sorted and you want faster than linear search.

Start at top-right and move left or down to narrow down the search quickly.