First and Last Occurrence of Element in DSA Javascript - Deep Dive

Overview - First and Last Occurrence of Element

What is it?

Finding the first and last occurrence of an element means locating where that element appears first and last in a list or array. This helps us know the range of positions where the element exists. We look through the list and note the earliest and latest spots of that element.

Why it matters

Without knowing the first and last occurrence, we might miss important information about how many times or where an element appears. This is useful in searching, counting, or grouping data. For example, in a list of dates, knowing the first and last time an event happened helps us understand its duration.

Where it fits

Before this, learners should understand arrays and basic searching methods. After this, they can learn about binary search for faster searching, or about frequency counting and range queries.

Mental Model

Core Idea

The first and last occurrence of an element mark the start and end positions where that element appears in a list.

Think of it like...

Imagine a row of mailboxes with letters inside. Finding the first and last occurrence of a letter is like spotting the first and last mailbox that contains that letter along the street.

Array: [2, 3, 5, 3, 7, 3, 9]
Element: 3
Positions: 1, 3, 5
First occurrence -> index 1
Last occurrence -> index 5

Build-Up - 7 Steps

1

Foundation

Understanding Array Indexing Basics

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

An array is a list of items stored in order. Each item has a position called an index, starting from 0. For example, in [10, 20, 30], 10 is at index 0, 20 at index 1, and 30 at index 2.

Result

You can access any element by its index, like array[1] gives 20.

Knowing how indexing works is essential because finding occurrences depends on checking each position.

2

Foundation

Linear Search to Find an Element

Concept: Learn to look through each element one by one to find a target value.

Start from the first element and check if it matches the target. If not, move to the next until you find it or reach the end. This is called linear search.

Result

If the target is 3 in [1, 3, 5], linear search finds it at index 1.

Linear search is simple and works on any list, but can be slow for large data.

3

Intermediate

Finding the First Occurrence of Element

🤔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 start and stop at the first match to find the first occurrence.

Loop through the array from index 0 upwards. When you find the element equal to the target, record that index and stop searching.

Result

For array [4, 2, 7, 2, 9], first occurrence of 2 is at index 1.

Stopping at the first match saves time and gives the earliest position of the element.

4

Intermediate

Finding the Last Occurrence of Element

🤔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 backwards and stop at the first match to find the last occurrence.

Loop through the array from the last index down to 0. When you find the element equal to the target, record that index and stop searching.

Result

For array [4, 2, 7, 2, 9], last occurrence of 2 is at index 3.

Scanning backwards ensures you find the latest position quickly without checking all elements.

5

Intermediate

Combined Search for Both Occurrences

🤔Before reading on: do you think searching separately or together is more efficient? Commit to your answer.

Concept: Find both first and last occurrences in one pass by tracking positions while scanning once.

Loop through the array once from start to end. When you find the target, if first occurrence is not set, set it. Always update last occurrence to current index. After loop ends, you have both positions.

Result

For [1, 3, 5, 3, 7, 3], first occurrence of 3 is 1, last occurrence is 5.

One pass reduces time compared to two separate scans, improving efficiency.

6

Advanced

Using Binary Search for Sorted Arrays

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

Concept: Binary search can be adapted to find first and last occurrences efficiently in sorted arrays.

Binary search divides the array repeatedly to find the target. To find first occurrence, when target is found, continue searching left half. For last occurrence, continue searching right half. This reduces time from linear to logarithmic.

Result

For sorted array [1, 2, 2, 2, 3], first occurrence of 2 is index 1, last occurrence is index 3.

Adapting binary search for boundaries is a powerful optimization for large sorted data.

7

Expert

Handling Edge Cases and Performance Tradeoffs

🤔Before reading on: do you think linear or binary search always performs better? Commit to your answer.

Concept: Understand when linear or binary search is better, and how to handle cases like missing elements or duplicates.

If array is unsorted, linear search is necessary. For sorted arrays, binary search is faster but requires careful boundary checks. Also, if element is missing, return -1 or null. Handling duplicates means carefully adjusting search boundaries.

Result

Correctly returns -1 if element not found, and accurate first/last indices if present.

Knowing tradeoffs and edge cases prevents bugs and ensures efficient, correct solutions.

Under the Hood

Linear search checks each element one by one, comparing with the target. Binary search divides the search space by half each time, using comparisons to decide which half to keep. For first and last occurrences, binary search modifies the stopping condition to continue searching even after finding the target to find boundaries.

Why designed this way?

Linear search is simple and works on any data but can be slow. Binary search requires sorted data but is much faster. The design balances simplicity and efficiency depending on data properties. Modifying binary search to find boundaries leverages its divide-and-conquer nature for precise results.

Linear Search:
Start -> [Check index 0] -> [Check index 1] -> ... -> [Found or end]

Binary Search for First Occurrence:
[Low, High]
  ↓
Mid = (Low+High)/2
If arr[Mid] == target:
  Move High to Mid-1 to find earlier occurrence
Else if arr[Mid] < target:
  Move Low to Mid+1
Else:
  Move High to Mid-1
Repeat until Low > High

Myth Busters - 3 Common Misconceptions

Quick: Does finding the first occurrence mean the last occurrence is the same? Commit yes or no.

Common Belief: If you find the element once, that position is both first and last occurrence.

Reality: The first occurrence is the earliest position, and the last occurrence is the latest; they can be different if the element appears multiple times.

Why it matters: Assuming one position for both leads to wrong range calculations and errors in counting or slicing data.

Quick: Is binary search always faster than linear search? Commit yes or no.

Common Belief: Binary search is always faster than linear search regardless of data.

Reality: Binary search requires sorted data; on unsorted data, linear search is necessary. Also, for very small arrays, linear search can be faster due to overhead.

Why it matters: Using binary search on unsorted data causes incorrect results; blindly choosing binary search wastes time and causes bugs.

Quick: Does scanning from the end always find the last occurrence faster? Commit yes or no.

Common Belief: Scanning from the end is always the best way to find the last occurrence.

Reality: While scanning from the end finds the last occurrence quickly, combining first and last search in one forward pass can be more efficient overall.

Why it matters: Choosing scanning direction without considering combined search can lead to unnecessary extra passes and slower code.

Expert Zone

1

Binary search for boundaries requires careful adjustment of low and high pointers to avoid infinite loops or off-by-one errors.

2

In some languages or environments, using built-in functions like lower_bound and upper_bound can simplify finding occurrences efficiently.

3

When data is very large, caching or indexing strategies can speed up repeated occurrence queries beyond simple search algorithms.

When NOT to use

Avoid binary search if the array is unsorted or changes frequently; use linear search or hash-based methods instead. For very large datasets with many queries, consider segment trees or binary indexed trees for range queries.

Production Patterns

In real systems, first and last occurrence searches appear in text search engines, event log analysis, and database indexing. Efficient boundary searches enable fast filtering and aggregation of data ranges.

Connections

Binary Search

Builds-on

Understanding first and last occurrence searches deepens knowledge of binary search adaptations for boundary problems.

Hash Maps

Alternative approach

Hash maps can store element positions for O(1) access to occurrences, offering a different strategy than searching.

Event Timeline Analysis (Data Science)

Application domain

Finding first and last occurrences in event logs helps analyze durations and frequencies, connecting algorithms to real-world data insights.

Common Pitfalls

#1 Stopping search immediately after finding the element without checking for earlier occurrences.

Wrong approach:

function firstOccurrence(arr, target) {
for(let i=0; i=0; i--) {
if(arr[i] === target) return i;
}
return -1;
}

Correct approach:

function firstOccurrence(arr, target) {
let result = -1;
for(let i=0; i=0; i--) {
if(arr[i] === target) {
result = i;
break;
}
}
return result;
}

Root cause:

Confusing immediate return with recording position; not considering that first or last occurrence requires scanning direction and stopping at correct time.

#2 Using binary search on unsorted arrays leading to wrong results.

Wrong approach:

function binarySearchFirst(arr, target) {
let low = 0, high = arr.length - 1;
while(low <= high) {
let mid = Math.floor((low + high) / 2);
if(arr[mid] === target) return mid;
else if(arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
// Used on unsorted array

Correct approach:

// Sort array first or use linear search
arr.sort((a,b) => a-b);
// Then use binary search
// Or use linear search directly if unsorted

Root cause:

Misunderstanding binary search requirement of sorted data.

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

Wrong approach:

function findFirst(arr, target) {
for(let i=0; i

Correct approach:

function findFirst(arr, target) {
for(let i=0; i

Root cause:

Forgetting to return a default value when target is missing.

Key Takeaways

First and last occurrences mark the earliest and latest positions of an element in a list, essential for range queries.

Linear search works on any array but can be slow; binary search is faster but requires sorted data and careful boundary handling.

Combining first and last occurrence search in one pass improves efficiency by reducing repeated scanning.

Handling edge cases like missing elements and duplicates is crucial for correct and robust solutions.

Understanding these searches connects to broader concepts like binary search adaptations, hash maps, and real-world data analysis.