First and Last Occurrence of Element in DSA Rust - Execution Trace

Concept Flow - First and Last Occurrence of Element

Start

↓

Initialize first = -1, last = -1

↓

Traverse array from i=0 to n-1

↓

Check if array[i

↓

If first == -1, set first = i

↓

Set last = i

↓

Continue traversal

↓

End traversal

↓

Return first and last

We scan the array once, updating first occurrence when we find the target first time, and last occurrence every time we find it.

Execution Sample

DSA Rust

let arr = [2, 3, 5, 3, 7];
let target = 3;
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;
    }
}

This code finds the first and last positions of 3 in the array.

Execution Table

Step	Index i	Element arr[i]	Condition arr[i] == target	first	last	Visual State
1	0	2	False	-1	-1	[2, 3, 5, 3, 7]
2	1	3	True	1	1	[2, 3, 5, 3, 7]
3	2	5	False	1	1	[2, 3, 5, 3, 7]
4	3	3	True	1	3	[2, 3, 5, 3, 7]
5	4	7	False	1	3	[2, 3, 5, 3, 7]
6	-	-	-	1	3	Traversal complete, first=1, last=3

💡 Traversal ends after last index; first and last occurrences found.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
first	-1	-1	1	1	1	1	1
last	-1	-1	1	1	3	3	3
i	-	0	1	2	3	4	-

Key Moments - 3 Insights

Why do we update 'last' every time we find the target, but 'first' only once?

Because 'first' stores the earliest index where target appears, so we set it only once (see step 2). 'last' updates every time to track the latest index (see steps 2 and 4).

What if the target is not in the array at all?

Both 'first' and 'last' remain -1, indicating target not found (no updates in execution_table).

Why do we continue traversing even after finding the first occurrence?

Because we need to find the last occurrence too, so we check all elements (see steps 3 to 5).

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'first' after step 4?

A 1

B 3

C -1

D 4

💡 Hint

Check the 'first' column at step 4 in the execution_table.

At which step does the condition 'arr[i] == target' become false for the last time?

A Step 1

B Step 5

C Step 3

D Step 6

💡 Hint

Look at the 'Condition arr[i] == target' column for the last 'False' before traversal ends.

If the target was 5 instead of 3, what would be the final value of 'last'?

A 3

B 1

C 2

D -1

💡 Hint

Check where 5 appears in the array and see the 'last' updates in variable_tracker.

Concept Snapshot

Find first and last occurrence by scanning array once.
Initialize first and last to -1.
Update first when target found first time.
Update last every time target found.
Return first and last after traversal.
If not found, both remain -1.

Full Transcript

To find the first and last occurrence of an element in an array, we start with two variables, first and last, set to -1. We scan the array from start to end. When we find the target element for the first time, we set first to that index. Every time we find the target, we update last to that index. After scanning all elements, first and last hold the earliest and latest positions of the target. If the target is not found, both remain -1. This method requires only one pass through the array, making it efficient.

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