First and Last Occurrence of Element in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does 'First Occurrence of Element' mean in an array?

It means finding the earliest position (smallest index) where a given element appears in the array.

beginner

What is the difference between 'First Occurrence' and 'Last Occurrence' of an element?

First Occurrence is the earliest index where the element appears; Last Occurrence is the latest index where the element appears in the array.

intermediate

Why is binary search useful for finding first and last occurrences in a sorted array?

Because binary search quickly narrows down the search space, allowing us to find the exact first or last position of an element in O(log n) time.

beginner

In Rust, what is a simple way to find the first occurrence of an element in a vector?

Use the iterator method `.iter().position(|&x| x == target)` which returns the index of the first matching element or None if not found.

beginner

How can you find the last occurrence of an element in a Rust vector?

Use `.iter().rposition(|&x| x == target)` which returns the index of the last matching element or None if not found.

What does the method `.position()` return when searching in a Rust vector?

A Index of the last element matching the condition

B Boolean if element exists

C Number of elements matching the condition

D Index of the first element matching the condition

`.position()` returns the index of the first element that satisfies the condition or None if no such element exists.

If an element does not exist in the array, what should the first and last occurrence functions return?

A -1 or None

B 0

C Length of the array

D The element itself

If the element is not found, returning -1 or None indicates absence clearly.

Which search method is faster for large sorted arrays to find first and last occurrences?

A Linear search

B Bubble search

C Binary search

D Random search

Binary search reduces search time to O(log n), making it faster than linear search for sorted arrays.

What does `.rposition()` do in Rust iterators?

A Finds the first matching element from the start

B Finds the last matching element from the end

C Counts matching elements

D Reverses the vector

`.rposition()` returns the index of the last element matching the condition, searching from the end.

In a sorted array with duplicates, what is the benefit of finding first and last occurrences?

A To count how many times the element appears

B To sort the array

C To remove duplicates

D To reverse the array

Knowing first and last occurrences helps calculate the total count of the element by subtracting indices.

Explain how you would find the first and last occurrence of an element in a sorted array using binary search.

Think about how to adjust the binary search when you find the element to continue searching left or right.

Describe how Rust iterator methods `.position()` and `.rposition()` help find first and last occurrences in a vector.

Consider how iterators scan from start or end and return optional indices.

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