Why First and Last Occurrence of Element in DSA C++?

The Big Idea

Discover how to find where something starts and ends in a list without endless searching!

The Scenario

Imagine you have a long list of names written on paper, and you want to find where a particular name first appears and where it appears last.

You start scanning from the top to find the first time the name shows up, then you scan again from the bottom to find the last time it appears.

The Problem

This manual scanning is slow and tiring, especially if the list is very long.

You might miss some occurrences or get confused about the exact positions.

Doing this repeatedly wastes time and can cause mistakes.

The Solution

Using the concept of finding the first and last occurrence of an element in a list with code helps you quickly and accurately find these positions.

The code can jump directly to the right spots without scanning the entire list multiple times.

Before vs After

✗ Before

int first = -1;
for (int i = 0; i < n; i++) {
  if (arr[i] == x) { first = i; break; }
}
int last = -1;
for (int i = n - 1; i >= 0; i--) {
  if (arr[i] == x) { last = i; break; }
}

✓ After

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

What It Enables

This lets you quickly find the exact start and end positions of any item in a list, enabling faster searching and better data handling.

Real Life Example

Think about searching for the first and last time a word appears in a book to understand its importance or theme.

Key Takeaways

Manually searching for first and last occurrences is slow and error-prone.

Code can find these positions efficiently in one pass.

This helps in quick data analysis and searching tasks.