First and Last Occurrence of Element in DSA Java - 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 know exactly where an item starts and ends in a sequence. We usually work with sorted or unsorted arrays to find these positions. The goal is to find these positions efficiently without checking every element one by one.

Why it matters

Without knowing the first and last occurrence, we might waste time searching through the entire list repeatedly or miss important information about the range of an element. This is important in tasks like searching logs, counting duplicates, or processing sorted data quickly. Efficiently finding these positions saves time and computing power, especially with large data.

Where it fits

Before this, you should understand arrays and basic searching techniques like linear search and binary search. After this, you can learn about frequency counting, range queries, and advanced searching algorithms like segment trees or binary indexed trees.

Mental Model

Core Idea

The first and last occurrence of an element mark the boundaries of where that element appears in a sequence, and finding them efficiently means narrowing down the search using comparisons.

Think of it like...

Imagine a row of identical books on a shelf mixed with other books. Finding the first and last occurrence is like spotting the first and last copy of your favorite book in that row without checking every single book.

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

Build-Up - 7 Steps

1

Foundation

Understanding Array Indexing Basics

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

An array is a list of elements stored one after another. Each element has an index starting from 0. For example, in array [5, 3, 8], 5 is at index 0, 3 at index 1, and 8 at index 2. You can access any element by its index directly.

Result

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

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

2

Foundation

Linear Search for Element Occurrence

Concept: Check each element one by one to find where the target appears first and last.

Start from the beginning of the array and move forward checking each element. When you find the target element for the first time, note that index as the first occurrence. Continue to the end to find the last occurrence by updating the index whenever you find the target again.

Result

You get the first and last positions of the element but may check every element.

Linear search is simple but can be slow for large arrays 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: Use binary search to find the first position of the element in a sorted array by narrowing the search space.

Binary search splits the array into halves repeatedly. To find the first occurrence, when you find the element, you don't stop. Instead, you continue searching the left half to see if the element appears earlier. This way, you find the earliest index where the element appears.

Result

You find the first occurrence efficiently in O(log n) time.

Knowing how to adjust binary search to find boundaries instead of any match is key to efficient searching.

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: Modify binary search to find the last position of the element by searching the right half after finding a match.

When binary search finds the element, instead of stopping, continue searching the right half to find if the element appears later. This finds the last occurrence index efficiently.

Result

You get the last occurrence in O(log n) time.

Adjusting the search direction after a match lets you pinpoint the last occurrence without scanning the whole array.

5

Intermediate

Combining First and Last Occurrence Searches

🤔Before reading on: do you think it's better to run one combined search or two separate binary searches for first and last occurrences? Commit to your answer.

Concept: Run two binary searches separately: one for the first occurrence and one for the last occurrence, then combine results.

Perform binary search twice: once to find the first occurrence and once to find the last occurrence. This approach is clean and efficient, giving both positions in O(log n) time each.

Result

You get both boundaries quickly without scanning the entire array.

Splitting the problem into two focused searches simplifies the logic and improves clarity.

6

Advanced

Handling Edge Cases and Non-Existent Elements

🤔Before reading on: if the element is not in the array, what should the first and last occurrence return? Commit to your answer.

Concept: Learn how to detect when the element is missing and return appropriate values like -1.

If binary search does not find the element, return -1 for both first and last occurrences. Also, handle cases where the element appears only once or at the edges of the array.

Result

Your function correctly reports absence and edge positions.

Handling edge cases prevents bugs and ensures your search works reliably in all situations.

7

Expert

Optimizing with Single Binary Search Variant

🤔Before reading on: do you think it's possible to find both first and last occurrences in a single binary search pass? Commit to your answer.

Concept: Use a single modified binary search that returns both boundaries by tracking potential positions during the search.

By carefully updating pointers and storing candidate indices during one binary search, you can find both first and last occurrences without running two separate searches. This requires more complex logic but reduces overhead.

Result

You get both occurrences in one pass with O(log n) time.

Understanding how to merge searches saves time and is useful in performance-critical applications.

Under the Hood

Binary search works by repeatedly dividing the search interval in half. It compares the middle element with the target and decides which half to continue searching. For first and last occurrences, the search continues even after finding the target, adjusting boundaries to find the earliest or latest index. Internally, this uses pointers or indices to track the current search range and candidate positions.

Why designed this way?

Binary search was designed to reduce search time from linear to logarithmic by exploiting sorted order. Extending it to find boundaries leverages the same divide-and-conquer principle but requires careful boundary updates to avoid missing earlier or later occurrences. Alternatives like linear search are simpler but inefficient for large data.

Initial array indices:
┌───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │
├───┼───┼───┼───┼───┼───┼───┤
│ 2 │ 4 │ 4 │ 4 │ 6 │ 7 │ 7 │
└───┴───┴───┴───┴───┴───┴───┘

Binary search steps:
[low=0, high=6]
mid=3 -> arr[3]=4 matches target
For first occurrence: move high=mid-1=2 to search left
For last occurrence: move low=mid+1=4 to search right
Repeat until low > high
Return stored candidate index

Myth Busters - 4 Common Misconceptions

Quick: Does binary search always find the first occurrence of an element? Commit yes or no.

Common Belief: Binary search always returns the first occurrence of the element.

Reality: Binary search returns any occurrence, not necessarily the first. You must modify it to find the first occurrence.

Why it matters: Assuming it returns the first occurrence leads to wrong answers when duplicates exist, causing bugs in range queries or counts.

Quick: If the element is not in the array, does binary search return -1 automatically? Commit yes or no.

Common Belief: Binary search returns -1 or an error if the element is not found.

Reality: Binary search returns the position where the element would be or ends with low > high, but you must explicitly check and return -1 if not found.

Why it matters: Not handling absence leads to incorrect indices and potential crashes or wrong data processing.

Quick: Is linear search always slower than binary search for finding occurrences? Commit yes or no.

Common Belief: Linear search is always slower than binary search for finding first and last occurrences.

Reality: Linear search can be faster for small or unsorted arrays where binary search is not applicable.

Why it matters: Blindly using binary search on unsorted data causes incorrect results; knowing when to use linear search avoids errors.

Quick: Can you find both first and last occurrences in a single binary search pass easily? Commit yes or no.

Common Belief: Finding both occurrences requires two separate binary searches.

Reality: With careful logic, a single binary search can find both boundaries, though it's more complex.

Why it matters: Knowing this allows optimization in performance-critical systems, reducing search overhead.

Expert Zone

1

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

2

In some languages or systems, integer overflow in calculating mid = (low + high) / 2 can cause bugs; using mid = low + (high - low) / 2 is safer.

3

When elements are very large or comparisons expensive, minimizing the number of comparisons by combining searches or caching results improves performance.

When NOT to use

Do not use binary search for first and last occurrences if the array is unsorted; use linear search instead. For very small arrays, linear search may be simpler and faster. If data changes frequently, consider data structures like balanced trees or hash maps for dynamic queries.

Production Patterns

In real systems, first and last occurrence searches are used in log analysis to find event ranges, in databases for range queries, and in text processing to find word boundaries. Often combined with caching and indexing for speed. Also used in competitive programming problems requiring fast frequency counts.

Connections

Binary Search Tree

Both use the divide-and-conquer principle to locate elements efficiently.

Understanding binary search helps grasp how binary search trees organize data for fast lookup and range queries.

Range Queries in Segment Trees

Finding first and last occurrences is a simple form of range query over arrays.

Knowing how to find boundaries prepares you to understand more complex range queries and updates in segment trees.

Signal Processing - Edge Detection

Detecting boundaries in arrays is similar to finding edges in signals where changes mark important positions.

Recognizing boundaries in data arrays connects to detecting significant changes in other fields like signal processing.

Common Pitfalls

#1 Stopping binary search immediately after finding the element.

Wrong approach:

int binarySearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid; // stops here
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}

Correct approach:

int firstOccurrence(int[] arr, int target) {
int low = 0, high = arr.length - 1, result = -1;
while (low <= high) {
int mid = low + (high - low) / 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 must continue after finding the target to find the first occurrence.

#2 Using binary search on unsorted arrays.

Wrong approach:

int binarySearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
// but arr is unsorted like [3, 1, 4, 2]

Correct approach:

int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}

Root cause:

Assuming binary search works on any array without sorting.

#3 Not checking if element exists before returning indices.

Wrong approach:

int first = firstOccurrence(arr, target);
int last = lastOccurrence(arr, target);
System.out.println("First: " + first + ", Last: " + last); // prints indices even if -1 missing not handled

Correct approach:

int first = firstOccurrence(arr, target);
int last = lastOccurrence(arr, target);
if (first == -1 || last == -1) System.out.println("Element not found");
else System.out.println("First: " + first + ", Last: " + last);

Root cause:

Forgetting to handle the case when the element is not present.

Key Takeaways

First and last occurrences mark the start and end positions of an element in an array, crucial for range queries and counting duplicates.

Binary search can find these occurrences efficiently by adjusting the search boundaries after finding the target.

Handling edge cases like missing elements and single occurrences ensures your search is robust and reliable.

Understanding how to modify binary search for boundaries unlocks many advanced searching and indexing techniques.

Knowing when to use linear search versus binary search prevents errors and improves performance in different scenarios.

Practice

1. What does the term first occurrence of an element in an array mean?

easy

A. The index of the first time the element appears in the array

B. The total count of the element in the array

C. The last index where the element appears

D. The sum of all elements before the element

Solution

1. Step 1: Understand the meaning of first occurrence

   The first occurrence is the earliest position where the element appears in the array, starting from index 0.

2. Step 2: Compare with other options

   Counting or last index are different concepts; sum is unrelated.

3. Final Answer:

   The index of the first time the element appears in the array -> Option A

4. Quick Check:

   First occurrence = first index found [OK]

Hint: First occurrence means earliest index found [OK]

Common Mistakes:

• Confusing first occurrence with count
• Mixing first occurrence with last occurrence
• Thinking it means sum or total

2. Which of the following Java code snippets correctly finds the first occurrence of target in array arr?

easy

A. for(int i=0; i

B. for(int i=arr.length-1; i>=0; i--) { if(arr[i] == target) return i; } return -1;

C. int index = arr.indexOf(target); return index;

D. while(arr.contains(target)) { return arr.indexOf(target); }

Solution

1. Step 1: Check loop direction and condition

   for(int i=0; i

2. Step 2: Analyze other options

   for(int i=arr.length-1; i>=0; i--) { if(arr[i] == target) return i; } return -1; loops backward, so finds last occurrence. int index = arr.indexOf(target); return index; uses invalid method for arrays. while(arr.contains(target)) { return arr.indexOf(target); } has incorrect syntax and logic.

3. Final Answer:

   for(int i=0; i -> Option A

4. Quick Check:

   Loop start to end returns first match [OK]

Hint: Loop from start to find first occurrence [OK]

Common Mistakes:

• Looping backward to find first occurrence
• Using methods not available for arrays
• Incorrect loop conditions

3. What is the output of the following Java code?

int[] arr = {5, 3, 7, 3, 9};
int target = 3;
int first = -1, last = -1;
for(int i=0; i

medium

A. First: 0, Last: 4

B. First: 1, Last: 3

C. First: 3, Last: 1

D. First: -1, Last: -1

Solution

1. Step 1: Trace the loop to find first and last indices

   At i=1, arr[1]=3 matches target, first=-1 so first=1, last=1. At i=3, arr[3]=3 matches, last=3 updated.

2. Step 2: Confirm final values

   First occurrence is index 1, last occurrence is index 3.

3. Final Answer:

   First: 1, Last: 3 -> Option B

4. Quick Check:

   First=1, Last=3 from loop [OK]

Hint: Update last on every match, first only once [OK]

Common Mistakes:

• Swapping first and last values
• Not updating last occurrence correctly
• Initializing first incorrectly

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

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

medium

A. Missing return type in method

B. Variable last is not initialized

C. Loop should run backwards from end to start

D. Break statement stops loop too early, finds first not last occurrence

Solution

1. Step 1: Analyze loop and break usage

   The break inside if stops loop at first match, so last is actually first occurrence, not last.

2. Step 2: Understand correct approach

   To find last occurrence, loop should continue through entire array without break, updating last each time.

3. Final Answer:

   Break statement stops loop too early, finds first not last occurrence -> Option D

4. Quick Check:

   Break stops loop early, wrong for last occurrence [OK]

Hint: Don't break loop when searching last occurrence [OK]

Common Mistakes:

• Using break inside loop for last occurrence
• Looping forward but breaking early
• Confusing first and last occurrence logic

5. Given a sorted array arr with possible duplicates, which approach efficiently finds the first and last occurrence of target in O(log n) time?

hard

A. Use a HashMap to store indices of all elements

B. Traverse array from start to end and record first and last indices

C. Use binary search twice: once for first occurrence, once for last occurrence

D. Sort the array again and then find occurrences

Solution

1. Step 1: Understand array is sorted

   Sorted array allows binary search to find elements quickly in O(log n) time.

2. Step 2: Apply binary search twice

   One binary search finds first occurrence by moving left on matches; another finds last occurrence by moving right.

3. Step 3: Compare with other options

   Linear traversal is O(n), HashMap adds overhead, sorting again is unnecessary.

4. Final Answer:

   Use binary search twice: once for first occurrence, once for last occurrence -> Option C

5. Quick Check:

   Binary search twice = O(log n) efficient [OK]

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

Common Mistakes:

• Using linear search on sorted array
• Trying to sort array again unnecessarily
• Using extra data structures without need