Search in 2D Matrix in DSA Rust - Time & Space Complexity

Time Complexity: Search in 2D Matrix

O(n * m)

Understanding Time Complexity

We want to understand how long it takes to find a number in a 2D matrix.

How does the search time grow as the matrix gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn search_matrix(matrix: &Vec>, target: i32) -> bool {
    for row in matrix {
        for &num in row {
            if num == target {
                return true;
            }
        }
    }
    false
}
    

This code checks every number in the matrix until it finds the target or finishes all elements.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each element in the matrix.
• How many times: Once for each element, until target is found or all checked.

How Execution Grows With Input

As the matrix size grows, the number of checks grows with the total elements.

Input Size (n x m)	Approx. Operations
10 x 10 (100)	Up to 100 checks
100 x 100 (10,000)	Up to 10,000 checks
1000 x 1000 (1,000,000)	Up to 1,000,000 checks

Pattern observation: The work grows proportionally to the total number of elements.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to search grows directly with the number of rows times columns.

Common Mistake

[X] Wrong: "Since each row is sorted, searching one row is always fast, so total search is O(n)."

[OK] Correct: The code checks every element without using sorting to skip parts, so it still may check all elements.

Interview Connect

Understanding this helps you explain how simple searches work and why using sorting or special methods can speed things up.

Self-Check

"What if the matrix rows and columns are sorted and we use a smarter search? How would the time complexity change?"

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