Search in 2D Matrix in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of binary search in 2D matrix

What is the output of the following Rust code that searches for the target 5 in a sorted 2D matrix?

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();
    let cols = matrix[0].len();
    let mut left = 0;
    let mut right = rows * cols - 1;
    while left <= right {
        let mid = (left + right) / 2;
        let mid_value = matrix[mid / cols][mid % cols];
        if mid_value == target {
            return true;
        } else if mid_value < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    false
}

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

A true

B false

C Runtime panic

D Compilation error

💡 Hint

Think about how the matrix is treated as a sorted list in the binary search.

The code treats the 2D matrix as a sorted 1D array by calculating mid index and accessing elements accordingly. Since 5 is present, it returns true.

❓ Predict Output

intermediate

Output when target is not in matrix

What will the output be when searching for target 13 in the same matrix using the given Rust function?

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();
    let cols = matrix[0].len();
    let mut left = 0;
    let mut right = rows * cols - 1;
    while left <= right {
        let mid = (left + right) / 2;
        let mid_value = matrix[mid / cols][mid % cols];
        if mid_value == target {
            return true;
        } else if mid_value < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    false
}

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

A true

B false

C Compilation error

D Runtime panic

💡 Hint

Check if 13 exists in the matrix.

Since 13 is not present in the matrix, the function returns false after exhausting the search.

🧠 Conceptual

advanced

Why binary search works on this 2D matrix

Why can we apply binary search on this 2D matrix as if it were a sorted 1D array?

A Because the matrix is square and has equal rows and columns

B Because the matrix is stored in contiguous memory locations

C Because the matrix elements are all unique

D Because each row is sorted and the first element of each row is greater than the last element of the previous row

💡 Hint

Think about the ordering of elements across rows.

The matrix is sorted such that each row is sorted and the first element of a row is greater than the last element of the previous row, allowing binary search treating it as a sorted list.

❓ Predict Output

advanced

Output of search with empty matrix

What is the output of the following Rust code when searching for any target in an empty matrix?

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();
    let cols = matrix[0].len();
    let mut left = 0;
    let mut right = rows * cols - 1;
    while left <= right {
        let mid = (left + right) / 2;
        let mid_value = matrix[mid / cols][mid % cols];
        if mid_value == target {
            return true;
        } else if mid_value < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    false
}

fn main() {
    let matrix: Vec<Vec<i32>> = vec![];
    println!("{}", search_matrix(matrix, 1));
}

A true

B Compilation error

C false

D Runtime panic

💡 Hint

Check the initial condition for empty matrix.

The function returns false immediately because the matrix is empty and has no elements to search.

❓ Predict Output

expert

Output of search with matrix containing duplicates

What is the output of the following Rust code when searching for target 3 in a matrix that contains duplicates?

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();
    let cols = matrix[0].len();
    let mut left = 0;
    let mut right = rows * cols - 1;
    while left <= right {
        let mid = (left + right) / 2;
        let mid_value = matrix[mid / cols][mid % cols];
        if mid_value == target {
            return true;
        } else if mid_value < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    false
}

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

A true

B false

C Compilation error

D Runtime panic

💡 Hint

Duplicates do not affect the binary search if the matrix is sorted properly.

The function returns true because 3 is present in the matrix, even if duplicated.

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