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.