First and Last Occurrence of Element in DSA Rust

Mental Model

Find where a number first appears and where it last appears in a list by checking each item one by one.

Analogy: Imagine a row of mailboxes with letters inside. You want to find the first and last mailbox that has a letter from your friend. You look from left to right to find the first mailbox, and from right to left to find the last mailbox.

Index: 0  -> 1  -> 2  -> 3  -> 4  -> 5  -> 6  -> null
Value: 1  -> 2  -> 3  -> 2  -> 4  -> 2  -> 5  -> null
          ↑search target=2

Dry Run Walkthrough

Input: list: [1, 2, 3, 2, 4, 2, 5], find first and last occurrence of 2

Goal: Find the first and last positions where 2 appears in the list

Step 1: Start scanning from the left to find the first 2

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Value: 1 -> [2] -> 3 -> 2 -> 4 -> 2 -> 5 -> null
First occurrence found at index 1

Why: We need to find the earliest position where 2 appears

Step 2: Continue scanning to update the last 2

Index: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Value: 1 -> 2 -> 3 -> 2 -> 4 -> [2] -> 5 -> null
Last occurrence found at index 5

Why: We need to find the latest position where 2 appears

Result:

First occurrence at index 1
Last occurrence at index 5

Annotated Code

DSA Rust

fn first_and_last_occurrence(arr: &[i32], target: i32) -> (Option<usize>, Option<usize>) {
    let mut first = None;
    let mut last = None;
    for (i, &val) in arr.iter().enumerate() {
        if val == target {
            if first.is_none() {
                first = Some(i); // record first occurrence
            }
            last = Some(i); // update last occurrence
        }
    }
    (first, last)
}

fn main() {
    let arr = [1, 2, 3, 2, 4, 2, 5];
    let target = 2;
    let (first, last) = first_and_last_occurrence(&arr, target);
    match first {
        Some(idx) => println!("First occurrence at index {}", idx),
        None => println!("Element not found"),
    }
    match last {
        Some(idx) => println!("Last occurrence at index {}", idx),
        None => println!("Element not found"),
    }
}

for (i, &val) in arr.iter().enumerate() {

iterate over array with index and value

if val == target {

check if current value matches target

if first.is_none() {

record first occurrence only once

first = Some(i); // record first occurrence

store index of first found target

last = Some(i); // update last occurrence

update last occurrence index each time target found

Output

First occurrence at index 1

Last occurrence at index 5

Complexity Analysis

Time: O(n) because we scan the list once from start to end

Space: O(1) because we only store two indices regardless of input size

vs Alternative: This is better than scanning twice (once from start and once from end), which would be O(2n). Here we do it in one pass.

Edge Cases

empty list

returns None for both first and last because target cannot be found

DSA Rust

for (i, &val) in arr.iter().enumerate() {

target not in list

returns None for both first and last because no match found

DSA Rust

if val == target {

target appears only once

first and last both return the same index

DSA Rust

if first.is_none() {

When to Use This Pattern

When asked to find the first and last place a value appears in a list, use a single pass scan updating first and last positions to solve efficiently.

Common Mistakes

Mistake: Scanning the list twice separately for first and last occurrence
Fix: Scan once and update both first and last indices during the same loop

Mistake: Not handling the case when the target is not found, leading to None unwrap errors
Fix: Use Option types and check if first or last is None before printing

Summary

Finds the first and last positions of a target element in a list.

Use when you need to know where a value starts and ends in a sequence.

Scan once, record first occurrence once, update last occurrence every time you find the target.

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