Search in 2D Matrix in DSA Javascript - Execution Trace

Concept Flow - Search in 2D Matrix

Start at top-right corner

↓

Compare target with current element

↓

Move left

↓

Check bounds

Yes/No↓

Return result

Start from the top-right element, compare with target, move left if target is smaller, move down if larger, repeat until found or out of bounds.

Execution Sample

DSA Javascript

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

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,3,5,7,15], [10,11,16,20,25], [23,30,34,50,60]]
2	Compare	(0,3)	7	7 > 5	Move left: col = 2	[[1,3,5,7,15], [10,11,16,20,25], [23,30,34,50,60]]
3	Compare	(0,2)	5	5 == 5	Found target	[[1,3,5,7,15], [10,11,16,20,25], [23,30,34,50,60]]
4	Return	-	-	-	-	Target found, search ends

💡 Target found at position (0,2), search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
row	0	0	0	0	0
col	4	3	2	2	2
current_element	15	7	5	5	5
found	false	false	false	true	true

Key Moments - 3 Insights

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

Because from the top-right, moving left decreases values and moving down increases values, allowing efficient elimination of rows or columns as shown in steps 1 and 2 of the execution_table.

What happens if the current element is greater than the target?

We move left by decreasing the column index, as seen in steps 1 and 2, because all elements below are larger, so moving down would not help.

Why do we stop when the row or column goes out of bounds?

Because it means we have checked all possible positions without finding the target, so the search ends as per the while loop condition in the code.

Visual Quiz - 3 Questions

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

A 2

B 3

C 4

D 1

💡 Hint

Check the 'Pointer Changes' and 'Current Position' columns in step 2 of the execution_table.

At which step does the search find the target?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for the row where 'Comparison with Target' shows equality in the execution_table.

If the target was 17 instead of 5, what would be the pointer change after step 1?

A Move left: col = 3

B Move down: row = 1

C Found target

D No pointer change

💡 Hint

Recall that if current element is less than target, we move down as per the code and concept_flow.

Concept Snapshot

Search in 2D Matrix:
- Start at top-right element (row=0, col=last)
- Compare element with target
- If element > target, move left (col--)
- If element < target, move down (row++)
- Repeat until found or out of bounds
- Efficient for sorted rows and columns

Full Transcript

This concept shows how to search a target value in a 2D matrix where each row and column is sorted. We start from the top-right corner and compare the current element with the target. If the current element is greater, we move left to smaller elements. If it is smaller, we move down to larger elements. We continue this until we find the target or run out of matrix bounds. The execution table traces each step, showing pointer movements and comparisons. This method efficiently narrows down the search space by eliminating rows or columns at each step.