Search in 2D Matrix in DSA Rust - Build from Scratch

Search in 2D Matrix

📖 Scenario: You are working with a grid of numbers, like a map of heights or temperatures. You want to find if a certain number exists in this grid.

🎯 Goal: Build a program that searches for a specific number in a 2D matrix and tells if it is found or not.

📋 What You'll Learn

Create a 2D vector called matrix with exact values

Create a variable called target with the number to search

Use nested for loops with variables row and col to search the matrix

Print "Found" if the target is in the matrix, otherwise print "Not Found"

💡 Why This Matters

🌍 Real World

Searching in 2D grids is common in games, maps, and image processing where you need to find specific values.

💼 Career

Understanding how to search in 2D data structures is important for software developers working with matrices, tables, or grid-based data.

1

Create the 2D matrix

Create a 2D vector called matrix with these exact rows: [1, 3, 5], [7, 9, 11], [13, 15, 17]

DSA Rust

# Create the 2D vector matrix with the given rows
# Your code here

Hint

Use vec![vec![...], vec![...], vec![...] ] to create a 2D vector.

2

Set the target number

Create a variable called target and set it to 9

DSA Rust

fn main() {
    let matrix = vec![
        vec![1, 3, 5],
        vec![7, 9, 11],
        vec![13, 15, 17],
    ];
    // Create target variable here
    // Your code here
}

Hint

Use let target = 9; to create the variable.

3

Search the matrix for the target

Use nested for loops with variables row and col to check each element in matrix. Create a boolean variable found set to false before loops. If matrix[row][col] equals target, set found to true and break both loops.

DSA Rust

fn main() {
    let matrix = vec![
        vec![1, 3, 5],
        vec![7, 9, 11],
        vec![13, 15, 17],
    ];
    let target = 9;
    // Add nested for loops and found variable here
    // Your code here
}

Hint

Use a label 'outer to break both loops when found.

4

Print the search result

Print "Found" if found is true, otherwise print "Not Found"

DSA Rust

fn main() {
    let matrix = vec![
        vec![1, 3, 5],
        vec![7, 9, 11],
        vec![13, 15, 17],
    ];
    let target = 9;
    let mut found = false;
    'outer: for row in 0..matrix.len() {
        for col in 0..matrix[row].len() {
            if matrix[row][col] == target {
                found = true;
                break 'outer;
            }
        }
    }
    // Print the result here
    // Your code here
}

Hint

Use if found { println!("Found"); } else { println!("Not Found"); }

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