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.

Practice

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

easy

A. Start from the bottom-left corner and move right or up based on comparison

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

C. Search each element row by row until the target is found

D. Use binary search on each row independently

Solution

1. Step 1: Understand matrix properties

   Since each row and column is sorted ascending, the top-right element is the largest in its row and smallest in its column.

2. Step 2: Use top-right corner to decide movement

   If the target is less than the current element, move left; if greater, move down. This efficiently narrows search space.

3. Final Answer:

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

4. Quick Check:

   Top-right corner search = Start from the top-right corner and move left or down based on comparison [OK]

Hint: Start at top-right, move left if bigger, down if smaller [OK]

Common Mistakes:

• Starting from bottom-left without adjusting moves correctly
• Searching row by row wastes time
• Using binary search on rows ignores column sorting

2. Which of the following TypeScript code snippets correctly initializes a 2D matrix of numbers?

easy

A. const matrix: number[][] = [[1,2,3],[4,5],[6,7,8,9]];

B. const matrix: number[] = [1,2,3,4,5,6,7,8,9];

C. const matrix: number[][] = [[1,2,3],[4,5,6],[7,8,9]];

D. const matrix: number[][] = [1,2,3,4,5,6,7,8,9];

Solution

1. Step 1: Check matrix type declaration

   TypeScript 2D array is declared as number[][]. const matrix: number[][] = [[1,2,3],[4,5,6],[7,8,9]];.

2. Step 2: Validate matrix structure

   const matrix: number[][] = [[1,2,3],[4,5,6],[7,8,9]]; has uniform rows with 3 elements each, valid for a matrix. const matrix: number[][] = [[1,2,3],[4,5],[6,7,8,9]]; has rows of different lengths, which is allowed but less common for matrices.

3. Final Answer:

   const matrix: number[][] = [[1,2,3],[4,5,6],[7,8,9]]; -> Option C

4. Quick Check:

   Proper 2D array syntax = const matrix: number[][] = [[1,2,3],[4,5,6],[7,8,9]]; [OK]

Hint: Use number[][] with nested arrays for 2D matrix [OK]

Common Mistakes:

• Using single array for 2D matrix
• Incorrect type declaration like number[] for 2D
• Mixing array elements without nested arrays

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

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

function searchMatrix(matrix: number[][], target: number): boolean {
  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, 5));

medium

A. Runtime error

B. false

C. undefined

D. true

Solution

1. Step 1: Start search from top-right corner

   Initial position is row=0, col=3 (value 11). Since 11 > 5, move left to col=2 (value 7).

2. Step 2: Compare and move accordingly

   7 > 5, move left to col=1 (value 4). 4 < 5, move down to row=1, col=1 (value 5). Found target 5, return true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Search finds 5 = true [OK]

Hint: Start top-right, move left if bigger, down if smaller [OK]

Common Mistakes:

• Not updating row and col correctly
• Returning false too early
• Confusing row and column indices

4. Identify the bug in this TypeScript function that searches a target in a sorted 2D matrix:

function searchMatrix(matrix: number[][], target: number): boolean {
  let row = 0;
  let col = matrix.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;
}

medium

A. col should be initialized to matrix[0].length - 1, not matrix.length - 1

B. row should start from matrix.length - 1

C. The while loop condition should use col < matrix[0].length

D. The function should return true at the end instead of false

Solution

1. Step 1: Check initialization of col variable

   col is set to matrix.length - 1, which is number of rows minus one, but columns count is matrix[0].length.

2. Step 2: Correct col initialization

   col should be matrix[0].length - 1 to point to the last column index in the first row.

3. Final Answer:

   col should be initialized to matrix[0].length - 1, not matrix.length - 1 -> Option A

4. Quick Check:

   col init must match columns count = col should be initialized to matrix[0].length - 1, not matrix.length - 1 [OK]

Hint: col index = last column, use matrix[0].length - 1 [OK]

Common Mistakes:

• Using rows count for column index
• Wrong loop conditions causing out-of-bounds
• Returning true instead of false when not found

5. Given a 2D matrix where each row and column is sorted ascending, how would you modify the search function to return the position [row, col] of the target if found, or [-1, -1] if not found? Choose the correct code snippet.

function searchMatrix(matrix: number[][], target: number): number[] {
  let row = 0;
  let col = matrix[0].length - 1;
  while (row < matrix.length && col >= 0) {
    if (matrix[row][col] === target) {
      // What to return here?
    } else if (matrix[row][col] > target) {
      col--;
    } else {
      row++;
    }
  }
  // What to return if not found?
}

hard

A. Return [row, col] inside if, and [-1, -1] after loop

B. Return [col, row] inside if, and [0, 0] after loop

C. Return true inside if, and false after loop

D. Return matrix[row][col] inside if, and null after loop

Solution

1. Step 1: Return position when target found

   Inside the if condition, return the current indices as [row, col] to indicate target position.

2. Step 2: Return [-1, -1] if target not found

   After the loop ends without finding target, return [-1, -1] to indicate absence.

3. Final Answer:

   Return [row, col] inside if, and [-1, -1] after loop -> Option A

4. Quick Check:

   Return position or [-1, -1] if missing = Return [row, col] inside if, and [-1, -1] after loop [OK]

Hint: Return indices when found, [-1, -1] if not found [OK]

Common Mistakes:

• Swapping row and col in return
• Returning boolean instead of position
• Returning wrong default value when not found