Search in 2D Matrix in DSA Python - Execution Trace

Concept Flow - Search in 2D Matrix

Start at top-right corner

↓

Compare target with current element

↓

Move down

↓

Check if inside matrix bounds

↓

Repeat or Stop

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

Execution Sample

DSA Python

matrix = [
  [1, 4, 7, 11],
  [2, 5, 8, 12],
  [3, 6, 9, 16],
  [10, 13, 14, 17]
]
target = 5
row, col = 0, len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
    if matrix[row][col] == target:
        print("Found")
        break
    elif matrix[row][col] < target:
        row += 1
    else:
        col -= 1
else:
    print("Not Found")

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

Execution Table

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

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

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4
row	0	0	0	1	1
col	3	2	1	1	1
current_element	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 > target, move left to smaller values; if current < target, move down to larger values. This is shown in execution_table steps 1 and 2.

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

Because the matrix rows are sorted left to right, moving left decreases the element value, helping us get closer to the target. See pointer changes in steps 1 and 2.

What happens if we reach outside matrix bounds without finding the target?

The loop ends and we conclude target is not found. This is the exit condition when row >= number of rows or col < 0, not shown here because target was found early.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current element at step 3?

A 7

B 4

C 5

D 11

💡 Hint

Check the 'Current Element' column at step 3 in execution_table.

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

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Pointer Changes' column to see when row increases.

If the target was 15 instead of 5, how would the pointer move after step 1?

A Move left (col decreases)

B Move down (row increases)

C Stop immediately

D Move up (row decreases)

💡 Hint

Compare target and current element at step 1, then check pointer changes logic.

Concept Snapshot

Search in 2D Matrix:
- Start at top-right element (row=0, col=last)
- If current == target: found
- If current < target: move down (row++)
- If current > target: move left (col--)
- Stop when out of bounds or found
- Works because rows and columns are sorted

Full Transcript

This visual trace shows how to search a target in a 2D matrix sorted by rows and columns. We start at the top-right corner and compare the current element with the target. If the current element is greater, we move left to smaller values. If smaller, we move down to larger values. We repeat this until we find the target or go outside the matrix bounds. The execution table tracks each step, showing positions, comparisons, and pointer moves. The variable tracker shows how row and column indices change. Key moments clarify why we start at top-right and how pointer moves help narrow the search. The quiz tests understanding of these steps. 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 an element in a 2D matrix where each row and column is sorted in ascending order?

easy

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

B. Start from bottom-left corner and move left or down based on comparison

C. Search each element one by one from left to right, top to bottom

D. Use binary search on each row independently

Solution

1. Step 1: Understand matrix properties and use top-right corner

   Each row and column is sorted ascending, so top-right element is largest in its row and smallest in its column. If target is less than current element, move left; if greater, move down.

2. Final Answer:

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

3. Quick Check:

   Top-right start = efficient search [OK]

Hint: Start at top-right to decide direction quickly [OK]

Common Mistakes:

• Starting from bottom-left without adjusting logic
• Searching all elements linearly
• Using binary search on each row without considering columns

2. Which of the following Python code snippets correctly initializes a 2D matrix named matrix with 3 rows and 4 columns filled with zeros?

easy

A. matrix = [[0]*4]*3

B. matrix = [[0]*3 for _ in range(4)]

C. matrix = [0]*3*[0]*4

D. matrix = [[0 for _ in range(4)] for _ in range(3)]

Solution

1. Step 1: Understand list comprehension for 2D matrix and check options

   Use nested list comprehension [[0 for _ in range(4)] for _ in range(3)] to create independent 3 rows with 4 zeros each. A shares references, B wrong dimensions, C syntax invalid.

2. Final Answer:

   matrix = [[0 for _ in range(4)] for _ in range(3)] -> Option D

3. Quick Check:

   Nested list comprehension = correct matrix init [OK]

Hint: Use nested list comprehension for independent rows [OK]

Common Mistakes:

• Using [[0]*4]*3 causes shared references
• Multiplying lists incorrectly
• Swapping rows and columns in comprehension

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

matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3

row, col = 0, len(matrix[0]) - 1
found = False
while row < len(matrix) and col >= 0:
    if matrix[row][col] == target:
        found = True
        break
    elif matrix[row][col] > target:
        col -= 1
    else:
        row += 1
print(found)

medium

A. IndexError

B. False

C. True

D. SyntaxError

Solution

1. Step 1: Trace starting position and comparisons until target found

   Start at top-right: matrix[0][3] = 7 > 3, move left to col=2; matrix[0][2] = 5 > 3, move left col=1; matrix[0][1] = 3 == target, found = True.

2. Final Answer:

   True -> Option C

3. Quick Check:

   Found target 3 = True [OK]

Hint: Start top-right, move left/down until found or out of bounds [OK]

Common Mistakes:

• Confusing row and column indices
• Not updating row or col correctly
• Assuming linear search needed

4. The following code is intended to search for a target in a sorted 2D matrix but does not work correctly. What is the error?

def search_matrix(matrix, target):
    row = 0
    col = len(matrix[0])
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return False

medium

A. col should start at len(matrix[0]) - 1, not len(matrix[0])

B. row should start at len(matrix) - 1

C. The while loop condition should use 'or' instead of 'and'

D. The function should return null instead of false

Solution

1. Step 1: Check initial column index and correct start

   col is set to len(matrix[0]) which is out of range (indexing starts at 0). It should be len(matrix[0]) - 1 to start at last valid column index.

2. Final Answer:

   col should start at len(matrix[0]) - 1, not len(matrix[0]) -> Option A

3. Quick Check:

   Index out of range fix = col start - 1 [OK]

Hint: Start col at last index: length minus one [OK]

Common Mistakes:

• Starting col at length causes IndexError
• Changing row start incorrectly
• Using wrong loop condition

5. Given a 2D matrix where each row and column is sorted ascending, write a function to count how many times a target number appears. Which approach is most efficient?

hard

A. Traverse entire matrix and count matches (O(m*n))

B. Use binary search on each row and sum counts (O(m*log n))

C. Start from top-right and move left/down counting matches (O(m+n))

D. Flatten matrix to 1D list and use built-in count method

Solution

1. Step 1: Analyze time complexities and correct approach

   Full traversal O(m*n), top-right single pass misses duplicates off the path, flatten O(m*n); binary search on each row finds leftmost/rightmost target positions to compute count per row, total O(m*log n) efficient and correct.

2. Final Answer:

   Use binary search on each row and sum counts (O(m*log n)) -> Option B

3. Quick Check:

   Binary per row = efficient count [OK]

Hint: Binary search range in each row [OK]

Common Mistakes:

• Using full traversal wasting time
• Flattening matrix loses sorted structure
• Top-right movement misses off-path duplicates