Search in 2D Matrix in DSA Typescript - Execution Trace

Concept Flow - Search in 2D Matrix

Start at top-right corner

↓

Compare target with current element

↓

Move left

↓

Repeat until found or out of bounds

↓

Result found or not

Start searching from the top-right corner of the matrix. Compare the target with the current element. If target is smaller, move left; if larger, move down. Repeat until found or out of bounds.

Execution Sample

DSA Typescript

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;
}

Searches for target in a sorted 2D matrix by starting at top-right and moving left or down.

Execution Table

Step	Operation	Current Position (row,col)	Current Element	Comparison with Target	Pointer Changes	Visual State
1	Start	(0,4)	15	15 > 5	Move left: col = 3	[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10,13,14,17,24], [18,21,23,26,30] ]
2	Compare	(0,3)	11	11 > 5	Move left: col = 2	[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10,13,14,17,24], [18,21,23,26,30] ]
3	Compare	(0,2)	7	7 > 5	Move left: col = 1	[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10,13,14,17,24], [18,21,23,26,30] ]
4	Compare	(0,1)	4	4 < 5	Move down: row = 1	[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10,13,14,17,24], [18,21,23,26,30] ]
5	Compare	(1,1)	5	5 == 5	Found target	[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10,13,14,17,24], [18,21,23,26,30] ]

💡 Target found at position (1,1), search ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5
row	0	0	0	0	1	1
col	4	3	2	1	1	1
current_element	15	11	7	4	5	5

Key Moments - 3 Insights

Why do we start searching from the top-right corner?

Starting at top-right lets us decide direction easily: if current element is greater than target, move left to smaller elements; if smaller, move down to larger elements. This is shown in steps 1-4 of the execution_table.

What happens if the target is not in the matrix?

The search moves left or down until pointers go out of matrix bounds (row >= rows or col < 0). Then the loop ends without finding the target. This is implied by the exit condition in the code.

Why do we move left when current element is greater than target?

Because the matrix rows are sorted ascending left to right, moving left leads to smaller elements, increasing chances to find the target. This is shown in steps 1-3 where col decreases.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'col' after step 3?

A 1

B 2

C 3

D 4

💡 Hint

Check the 'Pointer Changes' and 'Current Position' columns in step 3.

At which step does the search move down to the next row?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for 'Move down' in the 'Pointer Changes' column in the execution_table.

If the target was 20 instead of 5, what would happen at step 4?

A Move left to col = 0

B Move down to row = 1

C Found target

D Exit search

💡 Hint

Compare target with current element at step 4 and see the pointer movement logic.

Concept Snapshot

Search in 2D Matrix:
- Start at top-right element (row=0, col=last)
- While inside matrix bounds:
  - If element == target: return true
  - If element > target: move left (col--)
  - Else move down (row++)
- Return false if not found
- Works because rows and columns are sorted ascending

Full Transcript

This concept shows how to search a target number in a 2D matrix where each row and column is sorted ascending. We start at the top-right corner. If the current element is bigger than the target, we move left to smaller numbers. If smaller, we move down to bigger numbers. We repeat this until we find the target or go out of bounds. The execution table traces each step with current position, element, comparison, and pointer changes. Variables row and col track our position. Key moments clarify why we start at top-right and how pointer moves help find the target efficiently. The visual quiz tests understanding of pointer changes and movement decisions. This method is efficient because it uses the sorted property of the matrix to eliminate rows or columns each step.

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