Search in 2D Matrix in DSA Rust - Deep Dive

Overview - Search in 2D Matrix

What is it?

Searching in a 2D matrix means finding if a specific number or value exists inside a grid of rows and columns. The matrix is like a table with numbers arranged in rows and columns. We want to quickly check if the number is there without looking at every single element one by one. This helps us find answers faster in many problems involving grids or tables.

Why it matters

Without efficient search methods in a 2D matrix, programs would waste time checking every element, making them slow and frustrating. Many real-world problems like maps, games, or spreadsheets use 2D grids, so fast searching saves time and resources. It helps computers respond quickly and handle large data smoothly.

Where it fits

Before learning this, you should understand basic arrays and how to access elements in rows and columns. After this, you can learn more complex search algorithms like binary search in 2D or graph traversal techniques that work on grids.

Mental Model

Core Idea

Searching in a 2D matrix is like looking for a word in a crossword puzzle by moving row by row or using the matrix's sorted order to jump closer to the target.

Think of it like...

Imagine a library bookshelf arranged by author and then by book title. To find a book, you first find the right author shelf (row), then scan the titles (columns). If the shelves and titles are sorted, you can skip many books and find your target faster.

Matrix example:
┌─────────────┐
│ 1  3  5  7 │
│ 10 11 16 20│
│ 23 30 34 50│
└─────────────┘
Search process:
Start at top-right corner (7)
If target < 7, move left
If target > 7, move down
Repeat until found or out of bounds

Build-Up - 6 Steps

1

Foundation

Understanding 2D Matrix Structure

Concept: Learn what a 2D matrix is and how to access its elements using row and column indexes.

A 2D matrix is like a table with rows and columns. Each element is found by two numbers: row number and column number. For example, matrix[1][2] means second row, third column. You can think of it as a grid where you move down rows and across columns to find values.

Result

You can access any element in the matrix by specifying its row and column.

Understanding how to locate elements in a 2D matrix is the base for any search or manipulation in grids.

2

Foundation

Linear Search in 2D Matrix

Concept: Learn how to check every element one by one to find a target value.

Start from the first row and first column, check each element. If it matches the target, stop and return true. If you reach the end without finding it, return false. This is simple but slow for big matrices.

Result

You can find if a target exists by checking all elements, but it takes time proportional to total elements.

Linear search works everywhere but is inefficient for large matrices, motivating faster methods.

3

Intermediate

Using Sorted Rows for Faster Search

🤔Before reading on: do you think searching each row with binary search is faster than checking every element? Commit to yes or no.

Concept: If each row is sorted, you can use binary search on each row to find the target faster than linear search.

For each row, apply binary search: pick middle element, compare with target, move left or right half accordingly. Repeat until found or row ends. This reduces search time per row from linear to logarithmic.

Result

Searching each row with binary search speeds up the search compared to checking every element.

Knowing that sorted rows allow binary search helps reduce time complexity from O(rows*cols) to O(rows*log(cols)).

4

Intermediate

Search in Matrix with Sorted Rows and Columns

🤔Before reading on: if the matrix rows and columns are sorted, do you think starting from the top-left corner is best? Commit to yes or no.

Concept: When both rows and columns are sorted, start searching from the top-right or bottom-left corner to eliminate rows or columns quickly.

Start at top-right element. If target equals this element, return true. If target is smaller, move left (because all elements below are bigger). If target is bigger, move down (because all elements left are smaller). Repeat until found or out of bounds.

Result

This method finds the target in O(rows + cols) time, faster than searching every element.

Using the matrix's sorted property in two directions lets you discard large parts of the matrix each step.

5

Advanced

Binary Search Treating Matrix as 1D Array

🤔Before reading on: can you imagine treating a 2D matrix as a flat list for binary search? Commit to yes or no.

Concept: If the entire matrix is sorted as if flattened row-wise, you can apply binary search by mapping 1D index to 2D coordinates.

Calculate total elements = rows * cols. Use binary search on index from 0 to total-1. Convert mid index to row = mid / cols, column = mid % cols. Compare matrix[row][column] with target. Adjust search range accordingly.

Result

This method finds the target in O(log(rows*cols)) time, very efficient for large sorted matrices.

Mapping 2D to 1D index allows using classic binary search, leveraging full matrix sorting.

6

Expert

Rust Implementation with Safe Indexing and Early Exit

🤔Before reading on: do you think Rust's ownership and safety features affect how we write matrix search code? Commit to yes or no.

Concept: Implement the search in Rust using safe indexing, early returns, and clear control flow to avoid runtime errors and improve readability.

```rust fn search_matrix(matrix: &[Vec], target: i32) -> bool { if matrix.is_empty() || matrix[0].is_empty() { return false; } let rows = matrix.len(); let cols = matrix[0].len(); let mut row = 0; let mut col = cols - 1; while row < rows && col < cols { let val = matrix[row][col]; if val == target { return true; } else if val > target { if col == 0 { break; } col -= 1; } else { row += 1; } } 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)); } ```

Result

The program prints true because 3 is found in the matrix.

Rust's safety features guide writing clear, error-free code that handles edge cases like empty matrices and index underflow.

Under the Hood

The search uses the matrix's sorted property to eliminate rows or columns step-by-step. Starting at the top-right corner, each comparison decides whether to move left (to smaller numbers) or down (to larger numbers). This works because rows and columns are sorted ascending, so moving left decreases values and moving down increases values. Internally, this avoids checking every element by skipping impossible areas.

Why designed this way?

This approach was designed to improve search speed in sorted 2D data without flattening or extra memory. It balances simplicity and efficiency, avoiding complex data structures. Alternatives like flattening the matrix or searching each row separately are slower or use more space. This method leverages natural ordering to prune search space quickly.

Start at top-right:
┌─────┬─────┬─────┬─────┐
│  1  │  3  │  5  │  7  │ ← Start here
├─────┼─────┼─────┼─────┤
│ 10  │ 11  │ 16  │ 20  │
├─────┼─────┼─────┼─────┤
│ 23  │ 30  │ 34  │ 50  │
└─────┴─────┴─────┴─────┘
If target < current, move left
If target > current, move down
Repeat until found or out of bounds

Myth Busters - 3 Common Misconceptions

Quick: Does a sorted row guarantee the entire matrix is sorted? Commit yes or no.

Common Belief: If each row is sorted, the whole matrix is sorted like a single list.

Reality: Each row being sorted does not mean the entire matrix is sorted across rows. The last element of one row can be bigger or smaller than the first element of the next row.

Why it matters: Assuming full sorting leads to wrong search methods like single binary search on the whole matrix, causing incorrect results.

Quick: Is starting search from the top-left corner best for sorted rows and columns? Commit yes or no.

Common Belief: Starting from the top-left corner is the best place to search in a sorted matrix.

Reality: Starting from the top-right or bottom-left corner is better because it allows eliminating rows or columns each step based on comparisons.

Why it matters: Starting at top-left can cause inefficient search or complicated logic, slowing down the process.

Quick: Can binary search be applied directly if only rows are sorted but columns are not? Commit yes or no.

Common Belief: Binary search works on the entire matrix if each row is sorted, regardless of column order.

Reality: Binary search can only be applied row-wise, not on the whole matrix, if columns are unsorted.

Why it matters: Trying to binary search the whole matrix without full sorting leads to wrong answers or missed targets.

Expert Zone

1

The choice of starting point (top-right vs bottom-left) depends on matrix properties and can affect code simplicity.

2

Handling edge cases like empty matrices or single-row/column matrices is crucial to avoid runtime errors in production.

3

Rust's ownership and borrowing rules encourage writing safe, efficient search code that prevents common bugs like index underflow.

When NOT to use

This search method is not suitable if the matrix is unsorted or only partially sorted. In such cases, linear search or specialized algorithms like graph traversal or hash-based lookups are better alternatives.

Production Patterns

In real systems, this search is used in databases for range queries on sorted data, in geographic information systems for spatial queries, and in games for pathfinding on grids with sorted heuristics.

Connections

Binary Search

Builds-on

Understanding binary search in 1D arrays helps grasp how to apply it row-wise or on a flattened 2D matrix.

Graph Traversal

Alternative approach

When matrix sorting is absent, graph traversal algorithms like BFS or DFS help search connected cells efficiently.

Library Cataloging Systems

Similar pattern

Searching a sorted 2D matrix is like finding a book in a library sorted by author and title, showing how sorting helps narrow down search quickly.

Common Pitfalls

#1 Assuming the matrix is fully sorted row-wise and column-wise when only rows are sorted.

Wrong approach:

Applying binary search on the entire matrix as if it was a flat sorted list without checking column order.

Correct approach:

Apply binary search only on each individual sorted row separately.

Root cause:

Misunderstanding the sorting property of the matrix leads to wrong search assumptions.

#2 Starting search from top-left corner in a matrix sorted by rows and columns.

Wrong approach:

Starting at matrix[0][0] and moving right or down without a clear elimination strategy.

Correct approach:

Start at top-right corner and move left or down based on comparison to target.

Root cause:

Not realizing that top-right or bottom-left corners provide better elimination paths.

#3 Not handling empty matrix or zero columns, causing runtime errors.

Wrong approach:

Directly accessing matrix[0][0] without checking if matrix or rows are empty.

Correct approach:

Check if matrix.is_empty() or matrix[0].is_empty() before searching.

Root cause:

Overlooking edge cases leads to panics or crashes in real programs.

Key Takeaways

A 2D matrix search uses the matrix's sorted properties to find targets efficiently without checking every element.

Starting from the top-right or bottom-left corner allows eliminating rows or columns each step, speeding up search.

Binary search can be applied row-wise or on a flattened matrix if fully sorted, reducing time complexity.

Rust's safety features help write clear, error-free search code that handles edge cases gracefully.

Misunderstanding matrix sorting or starting points leads to inefficient or incorrect search results.

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