First and Last Occurrence of Element in DSA C++ - 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 and last positions when we find the target.

Execution Sample

DSA C++

int first = -1, last = -1;
for (int i = 0; i < n; i++) {
  if (arr[i] == target) {
    if (first == -1) first = i;
    last = i;
  }
}

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

Execution Table

Step	Index i	arr[i]	Condition arr[i]==target	first	last	Action	Visual State
1	0	5	No	-1	-1	No change	[5, 3, 7, 3, 9]
2	1	3	Yes	-1	-1	first=1, last=1	[5, 3, 7, 3, 9]
3	2	7	No	1	1	No change	[5, 3, 7, 3, 9]
4	3	3	Yes	1	1	last=3	[5, 3, 7, 3, 9]
5	4	9	No	1	3	No change	[5, 3, 7, 3, 9]
6	End	-	-	1	3	Traversal ends	[5, 3, 7, 3, 9]

💡 Reached end of array, traversal stops.

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 check if first == -1 before setting it?

Because first should store the earliest index where target appears. We only set it once, at the first occurrence (see Step 2 in execution_table).

Why do we update last every time we find the target?

Because last should always point to the most recent occurrence of target. This updates at every match (see Steps 2 and 4).

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

Then first and last remain -1, indicating no occurrence found (see Step 1 and final values).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'first' after Step 2?

A -1

B 1

C 0

D 3

💡 Hint

Check the 'first' column in row for Step 2 in execution_table.

At which step does 'last' get updated to 3?

A Step 4

B Step 5

C Step 3

D Step 2

💡 Hint

Look at the 'last' column and 'Action' in execution_table rows.

If the target was 7 instead of 3, what would be the final value of 'first'?

A 1

B -1

C 2

D 3

💡 Hint

Check where 7 appears in the array and how 'first' is set in execution_table.

Concept Snapshot

Find first and last occurrence of target in array:
- Initialize first and last to -1
- Traverse array once
- If arr[i] == target:
  - If first == -1, set first = i
  - Set last = i
- After traversal, first and last hold positions or -1 if not found

Full Transcript

This concept finds the first and last positions of a target element in an array by scanning it once. We start with first and last set to -1, meaning not found. As we move through the array, when we find the target, if first is still -1, we set it to the current index. We always update last to the current index when we find the target. After the loop ends, first and last tell us where the target first and last appeared. If the target is not found, both remain -1.