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.

Practice

1. What is the main idea behind searching a target value in a 2D matrix where each row and column is sorted in ascending order?

easy

A. Use binary search on each row independently

B. Start from bottom-left corner and move right or down based on comparison

C. Search each element one by one from top-left to bottom-right

D. Start from top-right corner and move left or down based on comparison

Solution

1. Step 1: Understand matrix properties

   Each row and column is sorted ascending, so top-right element is a good start to decide direction.

2. Step 2: Use top-right corner to guide search

   If target is less than current element, move left; if greater, move down.

3. Final Answer:

   Start from top-right corner and move left or down based on comparison -> Option D

4. Quick Check:

   Top-right start = efficient search [OK]

Hint: Start at top-right to decide move direction quickly [OK]

Common Mistakes:

• Searching all elements one by one wastes time
• Starting from bottom-left without clear logic
• Using binary search on each row ignores column sorting

2. Which of the following is the correct syntax to check if a target exists in a 2D matrix named matrix in JavaScript?

easy

A. for(let i=0; i

B. for(let i=0; i

C. for(let i=0; i

D. for(let i=0; i

Solution

1. Step 1: Identify correct loop ranges

   Outer loop runs over rows (matrix.length), inner loop over columns (matrix[0].length).

2. Step 2: Check element equality with strict equality

   Use === for exact match and return true if found.

3. Final Answer:

   for(let i=0; i -> Option B

4. Quick Check:

   Correct loop ranges and strict equality [OK]

Hint: Outer loop rows, inner loop columns, use === for comparison [OK]

Common Mistakes:

• Swapping row and column lengths in loops
• Using == instead of === causing type coercion
• Looping inner loop with wrong length causing errors

3. What will be the output of the following code snippet?

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

function searchMatrix(matrix, target) {
  let row = 0;
  let col = matrix[0].length - 1;
  while(row < matrix.length && col >= 0) {
    if(matrix[row][col] === target) return true;
    else if(matrix[row][col] > target) col--;
    else row++;
  }
  return false;
}

console.log(searchMatrix(matrix, target));

medium

A. Error

B. false

C. true

D. undefined

Solution

1. Step 1: Start from top-right element

   Initial position is matrix[0][3] = 11, compare with target 5.

2. Step 2: Move left since 11 > 5, now at matrix[0][2] = 7

   7 > 5, move left again to matrix[0][1] = 4.

3. Step 3: 4 < 5, move down to matrix[1][1] = 5

   Found target 5, return true.

4. Final Answer:

   true -> Option C

5. Quick Check:

   Top-right search finds 5 = true [OK]

Hint: Move left if bigger, down if smaller from top-right [OK]

Common Mistakes:

• Starting from wrong corner causing wrong moves
• Not updating row or column correctly
• Returning false too early without full search

4. Find the bug in the following code that searches for a target in a 2D matrix where rows and columns are sorted.

function searchMatrix(matrix, target) {
  let row = matrix.length - 1;
  let col = 0;
  while(row >= 0 && col < matrix[0].length) {
    if(matrix[row][col] === target) return true;
    else if(matrix[row][col] < target) row--;
    else col++;
  }
  return false;
}

medium

A. The directions to move row and col are swapped in conditions

B. The initial row and col values are incorrect

C. The while loop condition should use '||' instead of '&&'

D. The function should return false inside the loop

Solution

1. Step 1: Analyze movement logic

   Starting at bottom-left, if current < target, should move right (col++), else move up (row--).

2. Step 2: Check conditions in code

   Code moves row-- when current < target, which is wrong; it should move col++ instead.

3. Final Answer:

   The directions to move row and col are swapped in conditions -> Option A

4. Quick Check:

   Correct move directions fix search [OK]

Hint: From bottom-left, move right if smaller, up if bigger [OK]

Common Mistakes:

• Swapping row and column moves
• Wrong initial position for search
• Incorrect loop condition causing infinite loop

5. Given a 2D matrix where each row and column is sorted ascending, write a function to count how many times a target appears in the matrix efficiently. Which approach is best?

hard

A. Start from top-right and move left/down counting matches (O(m+n))

B. Traverse entire matrix counting matches (O(m*n))

C. Use binary search on each row and sum counts (O(m*log n))

D. Flatten matrix to 1D array and use binary search once (O(m*n))

Solution

1. Step 1: Understand time complexities

   Full traversal is slow (O(m*n)), binary search per row is better but still costly.

2. Step 2: Use top-right start to count efficiently

   Moving left/down lets you skip rows or columns, counting matches in O(m+n) time.

3. Final Answer:

   Start from top-right and move left/down counting matches (O(m+n)) -> Option A

4. Quick Check:

   Top-right traversal counts efficiently [OK]

Hint: Top-right start counts matches in linear time [OK]

Common Mistakes:

• Using full traversal wasting time
• Flattening matrix losing sorted structure
• Binary search per row misses column info