First and Last Occurrence of Element in DSA C++ - Deep Dive

Overview - First and Last Occurrence of Element

What is it?

Finding the first and last occurrence of an element means locating the earliest and latest positions where that element appears in a list or array. This helps us understand where a value starts and ends in a sequence. It is useful when the element may appear multiple times, and we want to know its range of presence. The positions are usually given as indexes starting from zero.

Why it matters

Without knowing the first and last occurrence, we might miss important information about how data is distributed. For example, in searching logs or records, knowing the range of an event helps in analysis and optimization. It also helps in algorithms that rely on ranges, like counting duplicates or segmenting data. Without this, we might do extra work or get wrong answers.

Where it fits

Before this, you should understand arrays or lists and basic searching techniques like linear search. After this, you can learn about binary search and how to optimize searching in sorted data. This topic builds a foundation for range queries and frequency counting in data structures.

Mental Model

Core Idea

The first and last occurrence of an element mark the boundaries of where that element appears in a sequence.

Think of it like...

Imagine a row of mailboxes where some have the same color. Finding the first and last occurrence is like spotting the first and last mailbox painted red in the row, marking the start and end of all red mailboxes.

Array: [2, 3, 3, 5, 3, 7, 8, 3]
Element: 3
Positions: 1, 2, 4, 7
First occurrence: index 1
Last occurrence: index 7

Index:  0   1   2   3   4   5   6   7
Value: [2,  3,  3,  5,  3,  7,  8,  3]
          ↑              ↑           
       first          last

Build-Up - 7 Steps

1

Foundation

Understanding Array Indexing Basics

Concept: Learn how elements are stored and accessed by their position in an array.

An array is a collection of elements stored in order. Each element has an index starting from 0. For example, in array [10, 20, 30], 10 is at index 0, 20 at index 1, and 30 at index 2. Accessing elements by index is direct and fast.

Result

You can find any element's position by its index number.

Understanding indexing is essential because first and last occurrences are all about positions in the array.

2

Foundation

Linear Search to Find an Element

Concept: Learn to scan the array from start to end to find if an element exists.

To find an element, check each position one by one. For example, to find 3 in [2, 3, 5], check index 0 (2), then index 1 (3). When found, stop or continue depending on need.

Result

You can tell if the element is present and where it first appears.

Linear search is simple and guarantees finding the element if it exists, but it can be slow for large arrays.

3

Intermediate

Finding First Occurrence by Scanning

🤔Before reading on: do you think scanning from start or end is better to find the first occurrence? Commit to your answer.

Concept: Scan the array from the beginning and stop at the first match to find the first occurrence.

Start at index 0 and move forward. When you find the element, record that index and stop. For example, in [2, 3, 3, 5], first occurrence of 3 is at index 1.

Result

You get the earliest position where the element appears.

Knowing to stop at the first match saves time and gives the exact first occurrence.

4

Intermediate

Finding Last Occurrence by Scanning

🤔Before reading on: do you think scanning from start or end is better to find the last occurrence? Commit to your answer.

Concept: Scan the array from the end and stop at the first match to find the last occurrence.

Start at the last index and move backward. When you find the element, record that index and stop. For example, in [2, 3, 3, 5, 3], last occurrence of 3 is at index 4.

Result

You get the latest position where the element appears.

Scanning backward ensures you find the last occurrence efficiently without checking all elements.

5

Intermediate

Combining First and Last Occurrence Search

🤔Before reading on: do you think it's better to scan twice or once to find both occurrences? Commit to your answer.

Concept: Use two scans: one from start for first occurrence, one from end for last occurrence.

First scan from start to find first occurrence. Second scan from end to find last occurrence. This is simple and works for unsorted arrays.

Result

You get both first and last positions of the element.

Separating the searches keeps logic simple and clear, though it may scan some elements twice.

6

Advanced

Optimizing with Binary Search on Sorted Arrays

🤔Before reading on: do you think binary search can find first and last occurrences directly? Commit to your answer.

Concept: Use binary search to find the first and last occurrence efficiently in sorted arrays.

Binary search divides the array repeatedly to find the element. To find first occurrence, when you find the element, continue searching left side. For last occurrence, continue searching right side. This reduces time from linear to logarithmic.

Result

You find first and last occurrences much faster in sorted arrays.

Knowing how to adjust binary search to find boundaries is key for performance in sorted data.

7

Expert

Handling Edge Cases and No Occurrence

🤔Before reading on: do you think the element always exists in the array? Commit to your answer.

Concept: Account for cases where the element is not present or appears only once.

If the element is not found, return -1 or a special value. If it appears once, first and last occurrence are the same index. Code must handle empty arrays and arrays with all same elements gracefully.

Result

Your solution is robust and handles all input cases correctly.

Anticipating edge cases prevents bugs and crashes in real-world applications.

Under the Hood

When searching for first or last occurrence, the program checks elements one by one or uses binary search to jump around. In linear search, it compares each element until it finds a match. In binary search, it repeatedly splits the array in half, comparing the middle element to the target, and narrows down the search range. For first occurrence, it moves left after a match; for last occurrence, it moves right. This uses the sorted property to reduce checks.

Why designed this way?

Linear search is simple and works for any array but can be slow. Binary search requires sorted data but is much faster. The design balances simplicity and efficiency. The approach to find first and last occurrence separately ensures correctness and clarity. Alternatives like hash maps exist but use extra memory and don't give positions directly.

Sorted Array: [1, 2, 3, 3, 3, 4, 5]
Target: 3

Binary Search Steps:
 ┌───────────────┐
 │Check middle at│
 │index 3 (3)    │
 └──────┬────────┘
        │
  Found 3, move left to find first occurrence
        ↓
 ┌───────────────┐
 │Check middle at│
 │index 1 (2)    │
 └──────┬────────┘
        │
  2 < 3, move right
        ↓
 ┌───────────────┐
 │Check middle at│
 │index 2 (3)    │
 └──────┬────────┘
        │
  Found 3, move left (left > right, stop)

First occurrence at index 2

Myth Busters - 4 Common Misconceptions

Quick: Does the first occurrence always appear before the last occurrence? Commit to yes or no.

Common Belief: The first occurrence is always at a smaller index than the last occurrence.

Reality: If the element appears only once, the first and last occurrence are the same index.

Why it matters: Assuming different indexes can cause errors when handling single occurrences, leading to wrong range calculations.

Quick: Can binary search be used on unsorted arrays to find occurrences? Commit to yes or no.

Common Belief: Binary search works on any array to find first and last occurrences quickly.

Reality: Binary search only works correctly on sorted arrays; on unsorted arrays it fails or gives wrong results.

Why it matters: Using binary search on unsorted data can cause incorrect answers and bugs.

Quick: Is scanning from start enough to find last occurrence? Commit to yes or no.

Common Belief: Scanning from the start and stopping at the first match gives the last occurrence too.

Reality: Scanning from start only finds the first occurrence; last occurrence requires scanning from the end or a different approach.

Why it matters: Mistaking first occurrence for last leads to wrong position reporting and logic errors.

Quick: Does the element always exist in the array? Commit to yes or no.

Common Belief: The element to find always exists in the array.

Reality: The element may not be present; code must handle this by returning a special value like -1.

Why it matters: Ignoring absence causes crashes or wrong outputs in programs.

Expert Zone

1

Binary search for first and last occurrence requires careful boundary updates to avoid infinite loops or missing the correct index.

2

In arrays with many duplicates, finding boundaries efficiently can improve performance significantly over naive scanning.

3

Returning both first and last occurrences together allows range-based algorithms to run faster by avoiding repeated searches.

When NOT to use

If the array is unsorted and performance is critical, consider using hash maps to store element positions instead of scanning. For very large data, indexing structures like segment trees or balanced trees may be better. Binary search is not suitable for unsorted data.

Production Patterns

In real systems, first and last occurrence searches are used in text editors to find word boundaries, in databases to locate record ranges, and in analytics to segment time series data. Optimized binary search variants are common in libraries and frameworks for fast lookups.

Connections

Binary Search

Builds-on

Understanding first and last occurrence deepens knowledge of binary search by showing how to adapt it to find boundaries, not just presence.

Range Queries in Data Structures

Same pattern

First and last occurrence define a range, which is a fundamental concept in segment trees and Fenwick trees for efficient queries.

Event Time Windows in Real-Time Systems

Analogous concept

Finding first and last occurrence is like identifying start and end times of events, helping in scheduling and monitoring.

Common Pitfalls

#1 Stopping search immediately after finding the element when looking for last occurrence.

Wrong approach:

for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i; // returns first occurrence, not last
}
}

Correct approach:

int last = -1;
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
last = i; // keep updating to get last occurrence
}
}
return last;

Root cause:

Confusing first occurrence logic with last occurrence; not continuing search after first match.

#2 Using binary search on unsorted array without sorting first.

Wrong approach:

int binarySearch(int arr[], int n, int x) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x) return mid;
else if (arr[mid] < x) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// Called on unsorted arr

Correct approach:

// Sort array first or use linear search
std::sort(arr, arr + n);
// Then use binary search

Root cause:

Misunderstanding that binary search requires sorted data.

#3 Not handling the case when element is not found, leading to returning uninitialized or wrong index.

Wrong approach:

int firstOccurrence(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) return i;
}
// No return if not found
}

Correct approach:

int firstOccurrence(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) return i;
}
return -1; // indicates not found
}

Root cause:

Forgetting to handle absence of element explicitly.

Key Takeaways

First and last occurrence locate the start and end positions of an element in a sequence, helping define its range.

Linear search works for any array but can be slow; binary search speeds up search in sorted arrays by dividing the search space.

Finding first occurrence scans from the start, last occurrence scans from the end or uses modified binary search to find boundaries.

Handling edge cases like element absence or single occurrence is essential for robust solutions.

Understanding these concepts builds a foundation for range queries and efficient data processing in many applications.