First and Last Occurrence of Element in DSA C++

Mental Model

Find where a number first appears and last appears in a list by checking each item from start to end.

Analogy: Imagine looking for a friend's name in a guest list. You note the first time you see their name and the last time it appears before the list ends.

Array: [2, 4, 4, 5, 4, 7]
Indexes:  0  1  2  3  4  5
We want to find first and last position of 4.

Dry Run Walkthrough

Input: list: [2, 4, 4, 5, 4, 7], element to find: 4

Goal: Find the first and last index where 4 appears in the list

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

[2, 4, 4, 5, 4, 7]
first = -1, last = -1

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

Step 2: Check element at index 1 (4), matches target

[2, 4, 4, 5, 4, 7]
first = 1, last = 1

Why: First time we see 4, record index 1 as first and last

Step 3: Check element at index 2 (4), matches target

[2, 4, 4, 5, 4, 7]
first = 1, last = 2

Why: Update last occurrence to index 2

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

[2, 4, 4, 5, 4, 7]
first = 1, last = 2

Why: No change, continue scanning

Step 5: Check element at index 4 (4), matches target

[2, 4, 4, 5, 4, 7]
first = 1, last = 4

Why: Update last occurrence to index 4

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

[2, 4, 4, 5, 4, 7]
first = 1, last = 4

Why: No change, end of list reached

Result:

Final: first occurrence = 1, last occurrence = 4

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

pair<int, int> findFirstAndLastOccurrence(const vector<int>& arr, int target) {
    int first = -1;
    int last = -1;
    for (int i = 0; i < (int)arr.size(); i++) {
        if (arr[i] == target) {
            if (first == -1) {
                first = i; // record first occurrence
            }
            last = i; // update last occurrence
        }
    }
    return {first, last};
}

int main() {
    vector<int> arr = {2, 4, 4, 5, 4, 7};
    int target = 4;
    pair<int, int> result = findFirstAndLastOccurrence(arr, target);
    cout << "First occurrence: " << result.first << "\n";
    cout << "Last occurrence: " << result.second << "\n";
    return 0;
}

for (int i = 0; i < (int)arr.size(); i++) {

iterate through each element to check for target

if (arr[i] == target) {

check if current element matches target

if (first == -1) { first = i; }

record first occurrence only once

last = i;

update last occurrence to current index

Output

First occurrence: 1

Last occurrence: 4

Complexity Analysis

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

Space: O(1) because we only store two indices regardless of input size

vs Alternative: Better than searching twice separately; this single pass finds both first and last occurrences efficiently

Edge Cases

empty list

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

DSA C++

for (int i = 0; i < (int)arr.size(); i++) {

target not in list

returns -1 for both first and last indicating absence

DSA C++

if (arr[i] == target) {

target appears only once

first and last both equal the single index where target appears

DSA C++

if (first == -1) { first = i; }

When to Use This Pattern

When asked to find first and last positions of an element in a list, use a single pass scan to track both positions efficiently.

Common Mistakes

Mistake: Stopping the search after finding the first occurrence and not updating the last occurrence
Fix: Continue scanning the entire list to update the last occurrence index

Mistake: Initializing first and last to 0 instead of -1, causing confusion when target is not found
Fix: Initialize first and last to -1 to clearly indicate target absence

Summary

Finds the first and last index where a target element appears in a list.

Use when you need to know the range of positions of an element in a sequence.

Remember to scan the whole list once, updating first only once and last every time you find the target.