Search in 2D Matrix in DSA Rust

Mental Model

We look for a number in a grid where each row and column is sorted. We use a smart way to skip parts of the grid quickly.

Analogy: Imagine a library with shelves sorted by book height from left to right and top to bottom. You start at the top-right corner and decide to move left or down based on the book height you want.

Matrix:
1  3  5  7
10 11 16 20
23 30 34 50

Start at top-right (7):
1  3  5  [7↑]
10 11 16 20
23 30 34 50

Dry Run Walkthrough

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

Goal: Find if 3 exists in the matrix

Step 1: Start at top-right element (7)

1  3  5  [7↑]
10 11 16 20
23 30 34 50

Why: We start here because it helps decide to move left or down

Step 2: Compare 7 with target 3, since 7 > 3, move left

1  3  [5↑] 7
10 11 16 20
23 30 34 50

Why: Moving left goes to smaller numbers

Step 3: Compare 5 with 3, since 5 > 3, move left

1  [3↑] 5  7
10 11 16 20
23 30 34 50

Why: Still bigger, so move left again

Step 4: Compare 3 with 3, found target

1  [3↑] 5  7
10 11 16 20
23 30 34 50

Why: Target found, stop search

Result:

1  [3↑] 5  7
10 11 16 20
23 30 34 50
Answer: true

Annotated Code

DSA Rust

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

fn main() {
    let matrix = vec![
        vec![1, 3, 5, 7],
        vec![10, 11, 16, 20],
        vec![23, 30, 34, 50],
    ];
    let target = 3;
    println!("{}", search_matrix(matrix, target));
}

while row < rows && col >= 0 {

loop while inside matrix bounds

if matrix[row as usize][col as usize] == target {

check if current element is target

return true;

found target, stop search

else if matrix[row as usize][col as usize] > target {

current element too big, move left

col -= 1; // move left

move left to smaller elements

else {

current element too small, move down

row += 1; // move down

move down to larger elements

Output

true

Complexity Analysis

Time: O(m + n) because we move at most m times down and n times left in the matrix

Space: O(1) because we use only a few variables, no extra space proportional to input

vs Alternative: Compared to searching each element (O(m*n)), this method is much faster by skipping parts of the matrix

Edge Cases

empty matrix

returns false immediately

DSA Rust

if matrix.is_empty() || matrix[0].is_empty() { return false; }

target smaller than smallest element

search ends quickly returning false

DSA Rust

while row < rows && col >= 0 { ... }

target larger than largest element

search ends quickly returning false

DSA Rust

while row < rows && col >= 0 { ... }

When to Use This Pattern

When you see a sorted 2D grid and need to find a value quickly, use the top-right corner search pattern to eliminate rows or columns fast.

Common Mistakes

Mistake: Starting search from bottom-left or top-left corner without adjusting moves
Fix: Start from top-right corner to decide moving left or down correctly

Mistake: Not checking matrix empty conditions causing runtime errors
Fix: Add guard to return false if matrix or first row is empty

Summary

Searches a sorted 2D matrix efficiently by starting at top-right and moving left or down.

Use when matrix rows and columns are sorted and you want to find if a target exists quickly.

The key is starting at top-right to eliminate rows or columns in each step.

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