Search in 2D Matrix in DSA Rust - Execution Trace

Concept Flow - Search in 2D Matrix

Start at top-right corner

↓

Compare target with current element

↓

Move left

↓

Check bounds

↓

Found?

Yes→Return True

No↓

Out of bounds?

Yes→Return False

↓

Repeat comparison

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

Execution Sample

DSA Rust

fn search_matrix(matrix: &Vec<Vec<i32>>, target: i32) -> bool {
    let (mut row, mut col): (usize, i32) = (0_usize, (matrix[0].len() as i32 - 1));
    while row < matrix.len() && col >= 0 {
        if matrix[row][col as usize] == target {
            return true;
        } else if matrix[row][col as usize] > target {
            col -= 1;
        } else {
            row += 1;
        }
    }
    false
}

Search target in sorted 2D matrix by starting at top-right and moving left/down based on comparison.

Execution Table

Step	Operation	Current Position (row,col)	Current Element	Comparison with Target	Pointer Changes	Visual State
1	Start	(0,4)	15	15 > 13	Move left: col = 3	[[1,3,5,7,15], [10,11,16,20,23], [23,30,34,50,60]]
2	Compare	(0,3)	7	7 < 13	Move down: row = 1	[[1,3,5,7,15], [10,11,16,20,23], [23,30,34,50,60]]
3	Compare	(1,3)	20	20 > 13	Move left: col = 2	[[1,3,5,7,15], [10,11,16,20,23], [23,30,34,50,60]]
4	Compare	(1,2)	16	16 > 13	Move left: col = 1	[[1,3,5,7,15], [10,11,16,20,23], [23,30,34,50,60]]
5	Compare	(1,1)	11	11 < 13	Move down: row = 2	[[1,3,5,7,15], [10,11,16,20,23], [23,30,34,50,60]]
6	Compare	(2,1)	30	30 > 13	Move left: col = 0	[[1,3,5,7,15], [10,11,16,20,23], [23,30,34,50,60]]
7	Compare	(2,0)	23	23 > 13	Move left: col = -1	[[1,3,5,7,15], [10,11,16,20,23], [23,30,34,50,60]]
8	Check bounds	(2,-1)	N/A	col < 0	Stop search	[[1,3,5,7,15], [10,11,16,20,23], [23,30,34,50,60]]

💡 Column index became -1, which is out of bounds, so target not found.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
row	0	0	1	1	1	2	2	2	2
col	4	3	3	2	1	1	0	-1	-1

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.

Why does the search stop when column index becomes -1?

Because column index -1 is outside the matrix bounds, meaning we've checked all possible positions in that row without finding the target, as shown in step 8 of the execution_table.

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

Because the matrix rows are sorted ascending left to right, so moving left leads to smaller elements, increasing chances to find the target, as seen in steps 1, 3, 4, 6, and 7.

Visual Quiz - 3 Questions

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

A 0

B 2

C 1

D 3

💡 Hint

Check the variable_tracker row values after step 3.

At which step does the column index become less than 0?

A Step 7

B Step 6

C Step 5

D Step 8

💡 Hint

Look at the pointer changes and current position in execution_table rows.

If the target was 16, at which step would the search find it?

A Step 5

B Step 4

C Step 3

D Step 6

💡 Hint

Check the current element and comparison in execution_table for step 4.

Concept Snapshot

Search in 2D Matrix (sorted rows and columns):
- Start at top-right element
- If current == target: return true
- If current > target: move left (col--)
- If current < target: move down (row++)
- Stop when out of bounds
- Time complexity: O(m + n)

Full Transcript

This concept shows how to search a target value in a 2D matrix where each row and column is sorted ascending. We start from the top-right corner. If the current element equals the target, we return true. If the current element is greater than the target, we move left to smaller elements. If it is smaller, we move down to larger elements. We repeat this until we find the target or go out of matrix bounds. The execution table traces each step with current position, element, comparison, and pointer changes. Variable tracker shows how row and column indices change. Key moments clarify why we start at top-right, why we move left or down, and when the search stops. The visual quiz tests understanding of these steps. This method efficiently searches in O(m+n) time.

Practice

1. What is the main idea behind searching a target value in a 2D matrix where each row is sorted and the first integer of each row is greater than the last integer of the previous row?

easy

A. Use binary search treating the matrix as a flattened sorted list

B. Search each row linearly from left to right

C. Search each column linearly from top to bottom

D. Use a hash map to store all elements for quick lookup

Solution

1. Step 1: Understand matrix sorting property

   Each row is sorted and the first element of a row is greater than the last element of the previous row, so the entire matrix can be seen as a sorted list.

2. Step 2: Apply binary search on the flattened matrix

   We can treat the matrix as a single sorted list and use binary search to find the target efficiently.

3. Final Answer:

   Use binary search treating the matrix as a flattened sorted list -> Option A

4. Quick Check:

   Matrix sorted row-wise + binary search = Use binary search treating the matrix as a flattened sorted list [OK]

Hint: Think of the matrix as one sorted list for binary search [OK]

Common Mistakes:

• Searching each row or column linearly wastes time
• Using hash map wastes extra space
• Ignoring the matrix's sorted property

2. Which Rust code snippet correctly calculates the middle index for binary search on a 2D matrix treated as a 1D array with total length `len`?

easy

A. let mid = (start + end) / 2;

B. let mid = start + (end - start) / 2;

C. let mid = (start - end) / 2;

D. let mid = (start * end) / 2;

Solution

1. Step 1: Avoid overflow in mid calculation

   Using `(start + end) / 2` can overflow if start and end are large. The safer way is `start + (end - start) / 2`.

2. Step 2: Check other options

   let mid = (start - end) / 2; subtracts incorrectly, and D multiplies which is wrong for mid calculation.

3. Final Answer:

   let mid = start + (end - start) / 2; -> Option B

4. Quick Check:

   Safe mid calculation = let mid = start + (end - start) / 2; [OK]

Hint: Use start + (end - start) / 2 to avoid overflow [OK]

Common Mistakes:

• Using (start + end) / 2 causing overflow
• Using subtraction incorrectly for mid
• Multiplying indices instead of averaging

3. Given the following Rust code to search for target 5 in a 2D matrix, what will be the printed output?

let matrix = vec![
    vec![1, 3, 5, 7],
    vec![10, 11, 16, 20],
    vec![23, 30, 34, 60]
];
let target = 5;
let rows = matrix.len();
let cols = matrix[0].len();
let mut start = 0;
let mut end = rows * cols - 1;
let mut found = false;
while start <= end {
    let mid = start + (end - start) / 2;
    let r = mid / cols;
    let c = mid % cols;
    if matrix[r][c] == target {
        found = true;
        break;
    } else if matrix[r][c] < target {
        start = mid + 1;
    } else {
        end = mid - 1;
    }
}
println!("{}", found);

medium

A. Runtime panic

B. false

C. Compilation error

D. true

Solution

1. Step 1: Understand binary search on matrix

   The code treats the matrix as a sorted list and uses binary search to find target 5.

2. Step 2: Trace the search for target 5

   5 is at matrix[0][2]. The binary search will find it and set found = true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Target 5 found = true [OK]

Hint: Map mid to row and col, then compare target [OK]

Common Mistakes:

• Confusing row and column calculation
• Off-by-one errors in indices
• Not updating start or end correctly

4. Identify the bug in this Rust code snippet that searches for a target in a 2D matrix and suggest the fix:

let matrix = vec![
    vec![1, 4, 7, 11],
    vec![15, 20, 25, 30],
    vec![35, 40, 45, 50]
];
let target = 20;
let rows = matrix.len();
let cols = matrix[0].len();
let mut start = 0;
let mut end = rows * cols;
while start <= end {
    let mid = start + (end - start) / 2;
    let r = mid / cols;
    let c = mid % cols;
    if matrix[r][c] == target {
        println!("Found");
        break;
    } else if matrix[r][c] < target {
        start = mid + 1;
    } else {
        end = mid - 1;
    }
}

medium

A. end should be rows * cols - 1 instead of rows * cols

B. start should be 1 instead of 0

C. Use while start < end instead of while start <= end

D. Calculate r and c as mid % cols and mid / cols respectively

Solution

1. Step 1: Check the range of end index

   Matrix has rows * cols elements, so last index is rows * cols - 1, not rows * cols.

2. Step 2: Fix end initialization

   Set end = rows * cols - 1 to avoid out-of-bound access when mid equals rows * cols.

3. Final Answer:

   end should be rows * cols - 1 instead of rows * cols -> Option A

4. Quick Check:

   Index range off-by-one fixed = end should be rows * cols - 1 instead of rows * cols [OK]

Hint: End index = total elements - 1 to avoid overflow [OK]

Common Mistakes:

• Setting end to rows * cols causing panic
• Swapping row and column calculations
• Incorrect loop condition

5. You have a 2D matrix where each row is sorted in ascending order, but the first integer of each row may be smaller than the last integer of the previous row. Which approach correctly searches for a target value efficiently?

hard

A. Use binary search on each row separately until target is found or all rows checked

B. Treat the matrix as a flattened sorted list and apply binary search once

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

D. Use a hash set to store all elements and check membership

Solution

1. Step 1: Understand matrix property

   Rows are sorted but no guarantee that first element of a row is greater than last of previous row, so flattened binary search won't work.

2. Step 2: Use stair-step search from top-right

   Starting at top-right, move left if current > target, move down if current < target, efficiently narrowing search.

3. Final Answer:

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

4. Quick Check:

   Stair-step search fits matrix property = Start from top-right corner and move left or down based on comparison [OK]

Hint: Start top-right, move left/down to find target fast [OK]

Common Mistakes:

• Assuming full matrix sorted for binary search
• Searching each row fully wasting time
• Using extra space unnecessarily