Search in 2D Matrix in DSA Go - 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

Start searching from the top-right corner. Move left if target is smaller, move down if target is larger, repeat until found or out of bounds.

Execution Sample

DSA Go

matrix := [][]int{{1,3,5},{7,9,11},{13,15,17}}
target := 9
row, col := 0, len(matrix[0])-1
for row < len(matrix) && col >= 0 {
  if matrix[row][col] == target { return true }
  else if matrix[row][col] > target { col-- }
  else { row++ }
}
return false

Search target 9 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 at top-right	(0,2)	5	5 < 9	Move down: row=1	[[1,3,5], [7,9,11], [13,15,17]]
2	Compare element	(1,2)	11	11 > 9	Move left: col=1	[[1,3,5], [7,9,11], [13,15,17]]
3	Compare element	(1,1)	9	9 == 9	Found target	[[1,3,5], [7,9,11], [13,15,17]]
4	Exit	-	-	-	-	Target found, search ends

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

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
row	0	1	1	1	1
col	2	2	1	1	1
current_element	5	11	9	9	9

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 (decrease column) to find smaller elements, as shown in step 2 where 11 > 9 and col changes from 2 to 1.

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

Because it means we have checked all possible positions without finding the target, so continuing would be invalid. This is implied by the loop condition in the code and the exit note.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current element at Step 2?

A 5

B 11

C 9

D 7

💡 Hint

Check the 'Current Element' column in execution_table row for Step 2.

At which step does the search find the target?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for 'Found target' in the 'Operation' column of execution_table.

If the target was 6 instead of 9, what would happen after Step 1?

A Move down to row=1

B Found target immediately

C Move left to col=1

D Move down to row=2

💡 Hint

Compare target 6 with current element 5 at Step 1 and decide pointer change.

Concept Snapshot

Search in 2D Matrix:
- Start at top-right element
- If current > target, move left
- If current < target, move down
- Repeat until found or out of bounds
- Efficient for matrices sorted row-wise and column-wise

Full Transcript

This visualization shows how to search a target in a 2D matrix sorted by rows and columns. We start at the top-right corner. If the current element is less than the target, we move down to a larger element. If it is greater, we move left to a smaller element. We repeat this until we find the target or run out of matrix bounds. The example searches for 9 in a 3x3 matrix, finding it at position (1,1) after three steps.