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.

Practice

1. What does the "First and Last Occurrence of Element" problem ask you to find in an array?

easy

A. The maximum and minimum elements in the array

B. The sum of all elements in the array

C. The first and last positions where a given element appears

D. The number of unique elements in the array

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the first and last positions of a specific element in an array.

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 C

4. Quick Check:

   First and last occurrence = positions of element [OK]

Hint: Look for earliest and latest index of element [OK]

Common Mistakes:

• Confusing with sum or max/min of array
• Returning count instead of positions
• Ignoring if element is not present

2. Which of the following C++ code snippets correctly finds the first occurrence of element x in vector arr?

easy

A. int first = 0; while(arr[first] != x) { first++; }

B. int first = -1; for(int i=0; i

C. int first = arr.size(); for(int i=0; i

D. int first = -1; for(int i=arr.size()-1; i>=0; i--) { if(arr[i] == x) { first = i; break; } }

Solution

1. Step 1: Check each option for correctness

   int first = -1; for(int i=0; i

2. Step 2: Identify errors in other options

   int first = 0; while(arr[first] != x) { first++; } may cause out-of-bound error if x not found; int first = arr.size(); for(int i=0; i=0; i--) { if(arr[i] == x) { first = i; break; } } finds last occurrence due to reverse loop.

3. Final Answer:

   int first = -1; for(int i=0; i -> Option B

4. Quick Check:

   Loop from start, break on first match = first occurrence [OK]

Hint: Loop forward, break on first match for first occurrence [OK]

Common Mistakes:

• Looping backward for first occurrence
• Not handling element not found case
• Using wrong initial index values

3. What will be the output of the following C++ code?

std::vector<int> arr = {2, 3, 5, 3, 7};
int x = 3;
int first = -1, last = -1;
for(int i=0; i<arr.size(); i++) {
  if(arr[i] == x) {
    if(first == -1) first = i;
    last = i;
  }
}
std::cout << first << " " << last << std::endl;

medium

A. 2 3

B. 0 4

C. 1 1

D. 1 3

Solution

1. Step 1: Trace the loop to find first and last occurrence of 3

   Indices: 0->2, 1->3, 2->5, 3->3, 4->7. First 3 at index 1, last 3 at index 3.

2. Step 2: Confirm output printed

   Prints first and last indices: 1 3.

3. Final Answer:

   1 3 -> Option D

4. Quick Check:

   First=1, Last=3 for element 3 [OK]

Hint: Track first set once, update last on every match [OK]

Common Mistakes:

• Confusing indices with values
• Not updating last occurrence correctly
• Printing values instead of indices

4. Identify the bug in this code snippet that tries to find the last occurrence of x in arr:

int last = -1;
for(int i=0; i<arr.size(); i++) {
  if(arr[i] = x) {
    last = i;
  }
}

medium

A. Using assignment (=) instead of comparison (==) in if condition

B. Loop should run backwards from end to start

C. Variable last should be initialized to 0

D. Missing break statement after finding last occurrence

Solution

1. Step 1: Check the if condition

   The condition uses single '=' which assigns x to arr[i], not compares.

2. Step 2: Understand impact of assignment in condition

   Assignment returns value of x, which may cause wrong behavior or infinite loop.

3. Final Answer:

   Using assignment (=) instead of comparison (==) in if condition -> Option A

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Use '==' for comparison, '=' is assignment [OK]

Common Mistakes:

• Confusing '=' and '==' in conditions
• Thinking loop direction causes bug here
• Assuming break needed for last occurrence

5. Given a sorted vector arr and an element x, which approach is the most efficient to find the first and last occurrence of x?

hard

A. Use binary search twice to find first and last positions

B. Use linear search from start to end

C. Sort the array again and then find occurrences

D. Use a hash map to store all indices of elements

Solution

1. Step 1: Understand the array is sorted

   Sorted array allows binary search to find elements efficiently.

2. Step 2: Use binary search twice

   One binary search finds first occurrence, another finds last occurrence in O(log n) time.

3. Step 3: Compare other options

   Linear search is O(n), sorting again is unnecessary, hash map adds extra space and complexity.

4. Final Answer:

   Use binary search twice to find first and last positions -> Option A

5. Quick Check:

   Sorted array + binary search = efficient first/last occurrence [OK]

Hint: Binary search twice on sorted array for first and last occurrence [OK]

Common Mistakes:

• Using linear search on sorted array
• Sorting array again unnecessarily
• Ignoring binary search advantages