Search in 2D Matrix in DSA Javascript

Mental Model

We look for a number in a grid where each row and column is sorted, moving step by step to find it quickly.

Analogy: Imagine searching for a book in a library where shelves are sorted by title from left to right and top to bottom. You start at the top-right corner and decide to move left or down depending on the book title you want.

Matrix:
1  4  7  11
2  5  8  12
3  6  9  16
10 13 14 17

Start at top-right corner:
1  4  7  [11↑]
2  5  8  12
3  6  9  16
10 13 14 17

Dry Run Walkthrough

Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]], target = 5

Goal: Find if 5 exists in the matrix

Step 1: Start at top-right element 11

1  4  7  [11↑]
2  5  8  12
3  6  9  16
10 13 14 17

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

Step 2: Compare 11 with 5, since 11 > 5, move left to 7

1  4  [7↑] 11
2  5  8  12
3  6  9  16
10 13 14 17

Why: Moving left goes to smaller numbers to find target

Step 3: Compare 7 with 5, since 7 > 5, move left to 4

1  [4↑] 7  11
2  5  8  12
3  6  9  16
10 13 14 17

Why: Still bigger, so move left again

Step 4: Compare 4 with 5, since 4 < 5, move down to 5

1  4  7  11
2  [5↑] 8  12
3  6  9  16
10 13 14 17

Why: Moving down goes to bigger numbers to find target

Step 5: Compare 5 with 5, found target

1  4  7  11
2  [5↑] 8  12
3  6  9  16
10 13 14 17

Why: Target found, stop search

Result:

1  4  7  11
2  [5↑] 8  12
3  6  9  16
10 13 14 17
Answer: true

Annotated Code

DSA Javascript

class MatrixSearcher {
  constructor(matrix) {
    this.matrix = matrix;
  }

  search(target) {
    if (this.matrix.length === 0 || this.matrix[0].length === 0) return false;
    let row = 0;
    let col = this.matrix[0].length - 1;

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

// Driver code
const matrix = [
  [1, 4, 7, 11],
  [2, 5, 8, 12],
  [3, 6, 9, 16],
  [10, 13, 14, 17]
];
const target = 5;
const searcher = new MatrixSearcher(matrix);
console.log(searcher.search(target));

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

loop while inside matrix bounds

const current = this.matrix[row][col];

get current element to compare

if (current === target) { return true; }

found target, stop search

else if (current > target) { col--; }

current too big, move left to smaller numbers

else { row++; }

current too small, move down to bigger numbers

Output

true

Complexity Analysis

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

Space: O(1) because we use only a few variables for row and column indices

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

Edge Cases

Empty matrix

Returns false immediately because no elements to search

DSA Javascript

if (this.matrix.length === 0 || this.matrix[0].length === 0) return false;

Target smaller than smallest element

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

DSA Javascript

else if (current > target) { col--; }

Target larger than largest element

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

DSA Javascript

else { 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 logic
Fix: Always start from top-right corner to decide moves based on comparisons

Mistake: Not checking matrix boundaries before accessing elements
Fix: Use loop conditions to ensure row and col indices stay within matrix limits

Summary

Searches a sorted 2D matrix for a target by moving left or down from the top-right corner.

Use when matrix rows and columns are sorted and you want efficient search.

Start at top-right and move left if current is too big, or down if too small.