First and Last Occurrence of Element in DSA Go - 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 Go

arr := []int{2, 3, 5, 3, 7}
target := 3
first, last := -1, -1
for i := 0; i < len(arr); i++ {
  if arr[i] == target {
    if first == -1 {
      first = i
    }
    last = i
  }
}

Find first and last index of target 3 in array [2,3,5,3,7]

Execution Table

Step	Operation	Index i	arr[i]	Condition arr[i]==target	first	last	Visual State
1	Initialize	-	-	-	-1	-1	[2, 3, 5, 3, 7]
2	Check arr[0]	0	2	False	-1	-1	[2, 3, 5, 3, 7]
3	Check arr[1]	1	3	True	1	1	[2, 3, 5, 3, 7]
4	Check arr[2]	2	5	False	1	1	[2, 3, 5, 3, 7]
5	Check arr[3]	3	3	True	1	3	[2, 3, 5, 3, 7]
6	Check arr[4]	4	7	False	1	3	[2, 3, 5, 3, 7]
7	End traversal	-	-	-	1	3	[2, 3, 5, 3, 7]

💡 Traversal ends after checking all elements; first=1 and last=3 are returned

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	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 set first only when it is -1?

Because first occurrence is the earliest index where target appears. Once set, we don't change it. See execution_table rows 3 and 5 where first is set only once.

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

Because last occurrence is the latest index where target appears. We keep updating last to current index when condition is true. See execution_table rows 3 and 5 where last changes.

What if the target is not found at all?

Both first and last remain -1, indicating target is absent. This is shown in execution_table row 2 when condition is false and no updates happen.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what are the values of first and last?

A first=-1, last=1

B first=1, last=-1

C first=1, last=1

D first=-1, last=-1

💡 Hint

Check the columns 'first' and 'last' in execution_table row with Step 3

At which step does the last occurrence get updated to index 3?

A Step 5

B Step 3

C Step 2

D Step 6

💡 Hint

Look at 'last' column changes in execution_table rows; last changes to 3 at Step 5

If the target was 10 (not in array), what would be the final values of first and last?

A first=0, last=0

B first=-1, last=-1

C first=4, last=4

D first=1, last=3

💡 Hint

Refer to key_moments about target absence and initial values in variable_tracker

Concept Snapshot

First and Last Occurrence of Element:
- Initialize first and last as -1
- Traverse array from start to end
- When element == target:
  - If first == -1, set first = current index
  - Always update last = current index
- 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. We start with first and last set to -1, meaning not found. We scan the array from left to right. When we find the target, if first is still -1, we set it to current index. We always update last to current index when target matches. After scanning all elements, first and last tell us the earliest and latest positions of the target. If target is not found, both remain -1. This method uses one pass and simple checks.