First and Last Occurrence of Element in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find first and last occurrence of 3 in a sorted array

What is the output of this Rust code that finds the first and last occurrence of the number 3 in the array?

DSA Rust

fn first_last_occurrence(arr: &[i32], target: i32) -> (i32, i32) {
    let mut first = -1;
    let mut last = -1;
    for (i, &val) in arr.iter().enumerate() {
        if val == target {
            if first == -1 {
                first = i as i32;
            }
            last = i as i32;
        }
    }
    (first, last)
}

fn main() {
    let arr = [1, 2, 3, 3, 3, 4, 5];
    let result = first_last_occurrence(&arr, 3);
    println!("({},{})", result.0, result.1);
}

A (3,5)

B (1,3)

C (-1,-1)

D (2,4)

💡 Hint

Remember that array indices start at 0 and the function scans from left to right.

The function scans the array and records the first and last index where the target 3 appears. The first 3 is at index 2 and the last at index 4.

❓ Predict Output

intermediate

Output when target is not in the array

What does this Rust code print when searching for 10 in the array?

DSA Rust

fn first_last_occurrence(arr: &[i32], target: i32) -> (i32, i32) {
    let mut first = -1;
    let mut last = -1;
    for (i, &val) in arr.iter().enumerate() {
        if val == target {
            if first == -1 {
                first = i as i32;
            }
            last = i as i32;
        }
    }
    (first, last)
}

fn main() {
    let arr = [1, 2, 3, 4, 5];
    let result = first_last_occurrence(&arr, 10);
    println!("({},{})", result.0, result.1);
}

A (1,1)

B (5,5)

C (-1,-1)

D (0,4)

💡 Hint

If the target is not found, the function returns (-1, -1).

Since 10 is not in the array, the function never updates first or last from -1.

🔧 Debug

advanced

Identify the error in this Rust code for first and last occurrence

What error does this Rust code produce when compiled?

DSA Rust

fn first_last_occurrence(arr: &[i32], target: i32) -> (i32, i32) {
    let mut first = -1;
    let mut last = -1;
    for i in 0..arr.len() {
        if arr[i] = target {
            if first == -1 {
                first = i as i32;
            }
            last = i as i32;
        }
    }
    (first, last)
}

fn main() {
    let arr = [1, 2, 3, 3, 4];
    let result = first_last_occurrence(&arr, 3);
    println!("({},{})", result.0, result.1);
}

A RuntimeError: index out of bounds

B SyntaxError: expected `==` but found `=` in if condition

C TypeError: mismatched types in assignment

D No error, prints (2,3)

💡 Hint

Check the if condition syntax for comparison.

The code uses a single = instead of == in the if condition, causing a syntax error.

❓ Predict Output

advanced

Output of binary search approach for first and last occurrence

What is the output of this Rust code that uses binary search to find first and last occurrence of 3?

DSA Rust

fn binary_search_first(arr: &[i32], target: i32) -> i32 {
    let mut low = 0;
    let mut high = arr.len() as i32 - 1;
    let mut result = -1;
    while low <= high {
        let mid = low + (high - low) / 2;
        if arr[mid as usize] == target {
            result = mid;
            high = mid - 1;
        } else if arr[mid as usize] < target {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    result
}

fn binary_search_last(arr: &[i32], target: i32) -> i32 {
    let mut low = 0;
    let mut high = arr.len() as i32 - 1;
    let mut result = -1;
    while low <= high {
        let mid = low + (high - low) / 2;
        if arr[mid as usize] == target {
            result = mid;
            low = mid + 1;
        } else if arr[mid as usize] < target {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    result
}

fn main() {
    let arr = [1, 2, 3, 3, 3, 4, 5];
    let first = binary_search_first(&arr, 3);
    let last = binary_search_last(&arr, 3);
    println!("({},{})", first, last);
}

A (2,4)

B (-1,-1)

C (0,6)

D (3,5)

💡 Hint

Binary search narrows down the range to find first and last positions.

Binary search finds the first 3 at index 2 and last 3 at index 4 correctly.

🧠 Conceptual

expert

Why binary search is preferred over linear search for first and last occurrence in sorted arrays?

Which of the following is the best reason to use binary search instead of linear search to find first and last occurrence of an element in a sorted array?

A Binary search has O(log n) time complexity, which is faster than linear search's O(n) for large arrays.

B Binary search uses less memory than linear search because it does not store indices.

C Linear search cannot find the last occurrence, only the first occurrence.

D Binary search works on unsorted arrays while linear search requires sorted arrays.

💡 Hint

Think about how many elements each method checks in large arrays.

Binary search reduces the search space by half each step, making it much faster than checking every element.

Practice

1. What does the "First and Last Occurrence of Element" problem ask you to find in a list?

easy

A. The first and last positions where a given element appears

B. The sum of all elements in the list

C. The maximum and minimum values in the list

D. The number of unique elements in the list

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the first and last positions of a specific element in a list.

2. Step 2: Identify what is required

   We need to locate the earliest and latest index where the element appears.

3. Final Answer:

   The first and last positions where a given element appears -> Option A

4. Quick Check:

   Positions = first and last occurrence [OK]

Hint: Look for earliest and latest index of element [OK]

Common Mistakes:

• Confusing with sum or count of elements
• Looking for max/min values instead
• Ignoring the order of occurrences

2. Which Rust code snippet correctly finds the first occurrence index of element target in vector v?

easy

A. v.iter().position(|&x| x == target)

B. v.iter().find(|&&x| x == target)

C. v.iter().filter(|&&x| x == target).count()

D. v.iter().last().position(|&x| x == target)

Solution

1. Step 1: Understand Rust iterator methods

   The position method returns the index of the first element matching the condition.

2. Step 2: Check each option

   v.iter().position(|&x| x == target) uses position correctly to find the first occurrence index. v.iter().find(|&&x| x == target) returns an Option<&T>, not index. v.iter().filter(|&&x| x == target).count() counts matches, not index. v.iter().last().position(|&x| x == target) is invalid because last() returns an element, not an iterator.

3. Final Answer:

   v.iter().position(|&x| x == target) -> Option A

4. Quick Check:

   position() returns first index [OK]

Hint: Use .position() to get first index [OK]

Common Mistakes:

• Using find() which returns element, not index
• Using count() which returns number of matches
• Trying to call position() after last() which is invalid

3. What is the output of this Rust code?

let v = vec![2, 3, 5, 3, 7];
let target = 3;
let first = v.iter().position(|&x| x == target);
let last = v.iter().rposition(|&x| x == target);
println!("[{:?}, {:?}]", first, last);

medium

A. [Some(2), Some(3)]

B. [Some(1), Some(4)]

C. [None, None]

D. [Some(1), Some(3)]

Solution

1. Step 1: Find first occurrence of 3 in vector

   Vector is [2, 3, 5, 3, 7]. The first 3 is at index 1.

2. Step 2: Find last occurrence of 3 in vector

   The last 3 is at index 3.

3. Final Answer:

   [Some(1), Some(3)] -> Option D

4. Quick Check:

   First = 1, Last = 3 [OK]

Hint: Use position() and rposition() for first and last [OK]

Common Mistakes:

• Confusing indices of first and last occurrences
• Using wrong iterator methods
• Forgetting that indices start at 0

4. Identify the error in this Rust code that tries to find the last occurrence of target in vector v:

let last = v.iter().position(|&x| x == target).unwrap();
println!("{}", last);

medium

A. unwrap() causes panic if element not found

B. v.iter() cannot be used with position()

C. Using position() finds first, not last occurrence

D. Missing semicolon after unwrap()

Solution

1. Step 1: Understand what position() returns

   position() returns the index of the first element matching the condition, not the last.

2. Step 2: Identify correct method for last occurrence

   To find the last occurrence, rposition() should be used instead of position().

3. Final Answer:

   Using position() finds first, not last occurrence -> Option C

4. Quick Check:

   position() = first occurrence, not last [OK]

Hint: Use rposition() for last occurrence, not position() [OK]

Common Mistakes:

• Using position() for last occurrence
• Ignoring unwrap() panic possibility
• Thinking iter() can't use position()

5. Given a sorted vector v with possible duplicates, which approach efficiently finds the first and last occurrence of target using binary search in Rust?

hard

A. Use find() method twice with different closures

B. Use two binary searches: one for first occurrence, one for last occurrence

C. Use a single linear scan from start to end

D. Use position() and rposition() on the entire vector

Solution

1. Step 1: Understand the vector is sorted with duplicates

   Binary search can be used to find positions efficiently in sorted data.

2. Step 2: Use two binary searches for first and last occurrence

   One binary search finds the first index where target appears, another finds the last index.

3. Final Answer:

   Use two binary searches: one for first occurrence, one for last occurrence -> Option B

4. Quick Check:

   Binary search twice for first and last [OK]

Hint: Binary search twice for first and last occurrence [OK]

Common Mistakes:

• Using linear scan on large sorted vector
• Using position() which is linear time
• Trying to find both occurrences in one binary search