First and Last Occurrence of Element in DSA Go

Mental Model

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

Analogy: Imagine looking through a row of books to find the first and last time a certain title shows up on the shelf.

Index: 0   1   2   3   4   5   6
List:  2 -> 3 -> 5 -> 3 -> 7 -> 3 -> 9
               ↑           ↑
           first?       last?

Dry Run Walkthrough

Input: list: [2, 3, 5, 3, 7, 3, 9], find first and last occurrence of 3

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

Step 1: Check element at index 0 (2), not 3

2 -> 3 -> 5 -> 3 -> 7 -> 3 -> 9
first: -1, last: -1

Why: We start from the beginning to find the first occurrence

Step 2: Check element at index 1 (3), found first occurrence

2 -> [3] -> 5 -> 3 -> 7 -> 3 -> 9
first: 1, last: -1

Why: First time we see 3, record index 1 as first occurrence

Step 3: Check element at index 2 (5), not 3

2 -> 3 -> 5 -> 3 -> 7 -> 3 -> 9
first: 1, last: -1

Why: Keep searching for last occurrence

Step 4: Check element at index 3 (3), update last occurrence

2 -> 3 -> 5 -> [3] -> 7 -> 3 -> 9
first: 1, last: 3

Why: Found 3 again, update last occurrence to index 3

Step 5: Check element at index 4 (7), not 3

2 -> 3 -> 5 -> 3 -> 7 -> 3 -> 9
first: 1, last: 3

Why: Continue searching for last occurrence

Step 6: Check element at index 5 (3), update last occurrence

2 -> 3 -> 5 -> 3 -> 7 -> [3] -> 9
first: 1, last: 5

Why: Found 3 again, update last occurrence to index 5

Step 7: Check element at index 6 (9), not 3

2 -> 3 -> 5 -> 3 -> 7 -> 3 -> 9
first: 1, last: 5

Why: Reached end of list, stop searching

Result:

2 -> 3 -> 5 -> 3 -> 7 -> 3 -> 9
first occurrence of 3 at index 1
last occurrence of 3 at index 5

Annotated Code

DSA Go

package main

import "fmt"

func firstAndLastOccurrence(arr []int, target int) (int, int) {
    first := -1
    last := -1
    for i, val := range arr {
        if val == target {
            if first == -1 {
                first = i // record first occurrence
            }
            last = i // update last occurrence
        }
    }
    return first, last
}

func main() {
    arr := []int{2, 3, 5, 3, 7, 3, 9}
    target := 3
    first, last := firstAndLastOccurrence(arr, target)
    fmt.Printf("List: %v\n", arr)
    fmt.Printf("First occurrence of %d at index %d\n", target, first)
    fmt.Printf("Last occurrence of %d at index %d\n", target, last)
}

for i, val := range arr {

iterate over each element to check for target

if val == target {

check if current element matches target

if first == -1 { first = i }

record first occurrence only once

last = i

update last occurrence whenever target found

Output

List: [2 3 5 3 7 3 9]

First occurrence of 3 at index 1

Last occurrence of 3 at index 5

Complexity Analysis

Time: O(n) because we scan the entire list once to find occurrences

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Better than searching twice separately for first and last because it uses one pass instead of two

Edge Cases

empty list

returns -1 for both first and last since target not found

DSA Go

for i, val := range arr {

target not in list

returns -1 for both first and last indicating no occurrence

DSA Go

if val == target {

target appears once

first and last both equal the single index where target appears

DSA Go

if first == -1 { first = i }

When to Use This Pattern

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

Common Mistakes

Mistake: Searching for first and last occurrences in separate loops doubling time
Fix: Combine both searches in one loop by updating first once and last every time target is found

Mistake: Not initializing first to -1 causing wrong first occurrence
Fix: Initialize first to -1 and only set it when target is found first time

Summary

Finds the first and last positions where a target number appears in a list.

Use when you need to know the range of positions for a value in a list quickly.

Remember to scan once, record first occurrence once, and update last occurrence every time.