First and Last Occurrence of Element in DSA Typescript - 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 within a sequence. It is useful when elements can repeat multiple times. The goal is to find these positions efficiently without checking every element unnecessarily.

Why it matters

Without knowing the first and last occurrence, we might waste time scanning the entire list multiple times or miss important information about the element's range. This concept helps in searching, counting, and analyzing data quickly, which is crucial in many real-world tasks like text search, event logs, or database queries. It saves time and computing power, making programs faster and more responsive.

Where it fits

Before learning this, you should understand arrays and basic searching techniques like linear search. After this, you can explore binary search and its variations for faster searching in sorted arrays. This topic builds a foundation for advanced searching and range query problems.

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 identical books on a shelf. The first occurrence is the position of the first copy of that book you see from the left, and the last occurrence is the position of the last copy you see before different books start.

Array: [2, 4, 4, 4, 5, 6, 6]
Element: 4
Positions: 0  1  2  3  4  5  6
           |  |  |  |  |  |  |
First occurrence of 4 is at index 1
Last occurrence of 4 is at index 3

Build-Up - 6 Steps

1

Foundation

Understanding Array Indexing Basics

Concept: Learn how elements are positioned and accessed in an array using indexes starting from zero.

An array is a list of elements stored in order. Each element has a position called an index, starting at 0 for the first element, 1 for the second, and so on. 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[0] gives 10.

Understanding indexing is essential because finding occurrences depends on knowing where elements sit in the array.

2

Foundation

Linear Search for Element Occurrence

Concept: Use a simple step-by-step check to find where an element appears in an array.

Start from the first element and check each one until you find the target element. The first time you find it is the first occurrence. To find the last occurrence, continue checking until the end and remember the last position where the element appeared.

Result

For array [1, 3, 3, 5], searching for 3 gives first occurrence at index 1 and last occurrence at index 2.

Linear search is easy to understand and works on any array but can be slow for large data because it checks every element.

3

Intermediate

Binary Search for First Occurrence

🤔Before reading on: do you think binary search can find the first occurrence directly or only any occurrence? Commit to your answer.

Concept: Modify binary search to find the earliest position of the element in a sorted array.

Binary search splits the array in half repeatedly to find an element quickly. To find the first occurrence, when you find the element, check if it's the first or if the same element appears before it. If it appears before, continue searching the left half; otherwise, return the current position.

Result

In [1, 2, 2, 2, 3], searching for 2 returns index 1 as the first occurrence.

Knowing how to adjust binary search to find boundaries makes searching much faster than linear search on sorted arrays.

4

Intermediate

Binary Search for Last Occurrence

🤔Before reading on: do you think finding the last occurrence is similar to the first? How would you change the search direction? Commit to your answer.

Concept: Adjust binary search to find the latest position of the element in a sorted array.

When binary search finds the element, check if it's the last or if the same element appears after it. If it appears after, continue searching the right half; otherwise, return the current position.

Result

In [1, 2, 2, 2, 3], searching for 2 returns index 3 as the last occurrence.

This step shows how small changes in search direction can find exact boundaries efficiently.

5

Advanced

Combined Function for Both Occurrences

🤔Before reading on: do you think it's better to write separate functions for first and last occurrence or combine them? Commit to your answer.

Concept: Create a single function that can find either the first or last occurrence based on a parameter.

Use a boolean flag to decide whether to search left (for first) or right (for last) when the element is found. This reduces code duplication and keeps logic clear.

Result

Calling the function with flag true returns first occurrence; with false returns last occurrence.

Combining logic improves code maintainability and clarity while preserving efficiency.

6

Expert

Handling Edge Cases and Unsorted Arrays

🤔Before reading on: do you think binary search works on unsorted arrays? What happens if the element is missing? Commit to your answer.

Concept: Understand limitations of binary search and how to handle missing elements or unsorted data.

Binary search requires sorted arrays; if unsorted, linear search is needed. If the element is missing, return -1 or a special value. Also, consider arrays with all elements the same or empty arrays.

Result

For unsorted array [3, 1, 2], binary search fails; linear search finds occurrences. Missing element returns -1.

Knowing when and how to handle special cases prevents bugs and ensures robust code.

Under the Hood

Binary search works by repeatedly dividing the search interval in half. It compares the target element with the middle element of the current interval. If they match, it checks if this is the boundary occurrence needed (first or last). If not, it narrows the search to the left or right half accordingly. This reduces the search space exponentially, making it very fast on sorted arrays.

Why designed this way?

Binary search was designed to improve search speed from linear time to logarithmic time on sorted data. The approach of adjusting the search direction when the element is found allows precise boundary detection without scanning the entire array. Alternatives like linear search are simpler but slower, and more complex data structures are not always needed.

Start
  │
  ▼
[Array Sorted]
  │
  ▼
Find middle element
  │
  ├─ If middle < target -> search right half
  ├─ If middle > target -> search left half
  └─ If middle == target ->
       ├─ For first occurrence: check if previous is same, else return
       └─ For last occurrence: check if next is same, else return
  │
  ▼
Repeat until boundaries found or search space empty

Myth Busters - 4 Common Misconceptions

Quick: Does binary search work correctly on unsorted arrays? Commit yes or no.

Common Belief: Binary search can be used on any array regardless of order.

Reality: Binary search only works correctly on sorted arrays.

Why it matters: Using binary search on unsorted arrays leads to incorrect results and wasted effort.

Quick: Is the first occurrence always the first time you find the element in binary search? Commit yes or no.

Common Belief: The first time binary search finds the element is the first occurrence.

Reality: Binary search may find any occurrence; extra checks are needed to find the first occurrence.

Why it matters: Assuming the first found is the first occurrence causes wrong index results.

Quick: If an element is not in the array, does binary search return a valid index? Commit yes or no.

Common Belief: Binary search always returns a valid index, even if the element is missing.

Reality: Binary search returns a special value (like -1) to indicate the element is not found.

Why it matters: Not handling missing elements properly can cause errors or wrong data access.

Quick: Can linear search be faster than binary search in some cases? Commit yes or no.

Common Belief: Binary search is always faster than linear search.

Reality: For very small or unsorted arrays, linear search can be faster or the only option.

Why it matters: Blindly using binary search without checking conditions can reduce performance.

Expert Zone

1

Binary search for boundaries requires careful index updates to avoid infinite loops or missing edge cases.

2

In some languages, integer overflow can occur when calculating mid = (low + high) / 2; using mid = low + Math.floor((high - low) / 2) avoids this.

3

When elements are repeated many times, binary search boundary methods can be combined with other data structures like segment trees for range queries.

When NOT to use

Do not use binary search for first and last occurrence on unsorted arrays; use linear search instead. For dynamic data where elements are inserted or deleted frequently, balanced trees or hash maps may be better. Also, if the array is very small, linear search might be simpler and faster.

Production Patterns

In real systems, first and last occurrence searches are used in text editors for find/replace features, in databases for range queries, and in event log analysis to find time intervals. Often combined with caching or indexing for speed. Also used in competitive programming to solve frequency and range problems efficiently.

Connections

Binary Search

Builds-on

Understanding first and last occurrence deepens knowledge of binary search variations and boundary conditions.

Range Queries in Data Structures

Builds-on

Knowing element boundaries helps in answering queries about counts or sums within ranges efficiently.

Event Time Interval Analysis (Data Science)

Similar pattern

Finding first and last occurrence is like finding start and end times of events, helping analyze durations and overlaps.

Common Pitfalls

#1 Assuming binary search returns the first occurrence without checking neighbors.

Wrong approach:

function firstOccurrence(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;
}

Correct approach:

function firstOccurrence(arr, target) {
let low = 0, high = arr.length - 1, result = -1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
result = mid;
high = mid - 1; // continue searching left
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}

Root cause:

Misunderstanding that binary search stops at any found element rather than the boundary.

#2 Using binary search on an unsorted array.

Wrong approach:

function lastOccurrence(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;
}

// Called on [3,1,4,2], target 2

Correct approach:

function lastOccurrence(arr, target) {
// Use linear search for unsorted arrays
let result = -1;
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) result = i;
}
return result;
}

Root cause:

Not verifying array sortedness before applying binary search.

#3 Not handling the case when the element is missing.

Wrong approach:

function firstOccurrence(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;
}
// No return here
}

Correct approach:

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

Root cause:

Forgetting to return a special value when the element is not found.

Key Takeaways

First and last occurrence locate the boundaries of an element's presence in a sequence.

Binary search can find these boundaries efficiently on sorted arrays by adjusting search direction.

Linear search works on any array but is slower for large data.

Handling edge cases like missing elements and unsorted arrays is crucial for correct results.

Combining first and last occurrence logic improves code clarity and maintainability.