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 within a collection. It is useful when elements can repeat multiple times and we want to know their range of presence.

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 a repeated event helps in analysis and decision-making. This concept makes searching efficient and precise, saving time and effort.

Where it fits

Before this, learners should understand arrays and basic searching techniques like linear search. After this, they can learn about binary search and advanced searching algorithms that improve speed, especially in sorted data.

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 of a color is like spotting the first and last mailbox painted that color in the row.

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

Build-Up - 7 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 items stored in order. Each item has a position called an index, starting at 0 for the first item. For example, in [5, 3, 8], 5 is at index 0, 3 at index 1, and 8 at index 2. Accessing elements by index lets us find or change values quickly.

Result

You can identify where each element lives in the array by its index number.

Understanding indexing is essential because finding occurrences depends on knowing where elements are located.

2

Foundation

Linear Search for Element Position

Concept: Learn to scan an array from start to end to find the position of a target element.

To find if an element exists, check each item one by one from the beginning. If the element matches the target, record its index. For example, searching for 4 in [2, 4, 6] checks 2 (no), then 4 (yes, index 1).

Result

You get the index of the first matching element or know it doesn't exist.

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

3

Intermediate

Finding First Occurrence Using Linear Search

🤔Before reading on: Do you think scanning from start to end always finds the first occurrence correctly? Commit to yes or no.

Concept: Modify linear search to stop at the first match to get the earliest position of the element.

Start from index 0 and move forward. When you find the element, stop and return that index. This guarantees the first occurrence because you never skip earlier matches.

Result

The index returned is the first place the element appears in the array.

Stopping early saves time and ensures you don't miss the earliest position.

4

Intermediate

Finding Last Occurrence Using Linear Search

🤔Before reading on: Is it better to scan from start to end or end to start to find the last occurrence? Commit to your answer.

Concept: Scan the array to find the last position where the element appears by checking all elements and updating the last found index.

Go through the array from start to end. Each time you find the element, update a variable with that index. After finishing, the variable holds the last occurrence index. Alternatively, scan from the end and stop at the first match.

Result

You get the index of the last place the element appears.

Tracking the last found index ensures you don't miss later occurrences.

5

Intermediate

Binary Search for First and Last Occurrence

🤔Before reading on: Can binary search find first and last occurrences directly or only any occurrence? Commit to your answer.

Concept: Use binary search on sorted arrays to find first and last occurrences efficiently by adjusting search boundaries.

Binary search splits the array in half repeatedly to find the element quickly. To find the first occurrence, when you find the element, continue searching the left half to check for earlier matches. For the last occurrence, continue searching the right half after a match. This narrows down exact boundaries.

Result

You get the first and last indexes in O(log n) time instead of scanning all elements.

Binary search leverages sorted order to speed up finding boundaries of repeated elements.

6

Advanced

Implementing First and Last Occurrence in C#

🤔Before reading on: Do you think one function can find both first and last occurrences or separate functions are needed? Commit to your answer.

Concept: Write clear, reusable C# functions using binary search to find first and last occurrences separately.

Use two functions: one to find the first occurrence by moving left when a match is found, and one to find the last occurrence by moving right. Both use while loops and index pointers. This approach is clean and efficient for sorted arrays.

Result

Functions return correct first and last indexes or -1 if element not found.

Separating concerns in code improves readability and correctness in production.

7

Expert

Handling Edge Cases and Performance Considerations

🤔Before reading on: Should you always use binary search for first and last occurrences regardless of array size? Commit to your answer.

Concept: Understand how to handle empty arrays, elements not present, all elements same, and when linear search might be better.

Check if array is empty before searching. If element is not found, return -1. If all elements are the same, first is 0 and last is length-1. For very small arrays, linear search may be simpler and faster due to overhead. Also, consider stability and thread safety in concurrent environments.

Result

Robust code that handles all input cases correctly and performs well.

Knowing when and how to handle edge cases prevents bugs and improves reliability.

Under the Hood

Binary search works by repeatedly dividing the search interval in half. For first occurrence, when a match is found, the search continues on the left half to find earlier matches. For last occurrence, it continues on the right half. This uses index pointers and loop conditions to narrow down the exact boundary positions.

Why designed this way?

This method was designed to efficiently find boundaries in sorted data without scanning every element. Linear search is simple but slow for large data. Binary search exploits order to reduce time from linear to logarithmic, a huge performance gain.

Start
  ↓
[Low = 0, High = n-1]
  ↓
Calculate Mid = (Low + High) / 2
  ↓
Is element at Mid == target?
  ├─ Yes -> For first occurrence: High = Mid - 1 (search left)
  │           For last occurrence: Low = Mid + 1 (search right)
  └─ No -> If element < target: Low = Mid + 1
           Else: High = Mid - 1
  ↓
Repeat until Low > High
  ↓
Return boundary index or -1 if not found

Myth Busters - 4 Common Misconceptions

Quick: Does finding any occurrence of an element guarantee you have found the first occurrence? Commit to yes or no.

Common Belief: If you find the element once, that must be the first occurrence.

Reality: The first found occurrence might be in the middle; earlier occurrences could exist before it.

Why it matters: Assuming the first found is the first occurrence can cause wrong results, especially in sorted arrays where multiple duplicates exist.

Quick: Is binary search always faster than linear search for any array size? Commit to yes or no.

Common Belief: Binary search is always the fastest method to find elements.

Reality: For very small arrays, linear search can be faster due to less overhead and simpler operations.

Why it matters: Blindly using binary search can waste time and resources on small data where simpler methods suffice.

Quick: Can you use binary search to find first and last occurrences in unsorted arrays? Commit to yes or no.

Common Belief: Binary search works on any array regardless of order.

Reality: Binary search requires the array to be sorted; otherwise, it won't find correct positions.

Why it matters: Using binary search on unsorted data leads to incorrect results and bugs.

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

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

Reality: Both scanning directions take linear time; the difference is negligible unless the element is near the end.

Why it matters: Over-optimizing scan direction can complicate code without meaningful performance gain.

Expert Zone

1

Binary search for boundaries requires careful adjustment of mid calculation and loop conditions to avoid infinite loops or off-by-one errors.

2

In concurrent or multi-threaded environments, array contents might change during search, requiring synchronization or immutable data structures.

3

When elements are very frequent, caching first and last occurrence results can optimize repeated queries.

When NOT to use

Avoid binary search for first and last occurrences if the array is unsorted or very small; use linear search instead. For dynamic data that changes frequently, consider balanced trees or hash maps for faster updates and queries.

Production Patterns

In real systems, first and last occurrence searches appear in log analysis, event tracking, and database indexing. Implementations often combine binary search with caching layers and handle edge cases explicitly for robustness.

Connections

Binary Search

Builds-on

Understanding first and last occurrence deepens knowledge of binary search by applying it to find exact boundaries, not just any match.

Range Queries in Data Structures

Related pattern

Finding first and last occurrences is a simple form of range query, which is foundational in segment trees and interval trees.

Event Timeline Analysis (Social Sciences)

Cross-domain analogy

Locating first and last occurrences in data is like identifying start and end points of events in timelines, helping analyze durations and patterns.

Common Pitfalls

#1 Returning the index immediately upon finding the element without checking if it's the first occurrence.

Wrong approach:

int FindFirst(int[] arr, int target) {
for (int i = 0; i < arr.Length; i++) {
if (arr[i] == target) return i; // returns first found, but not always first occurrence in sorted array
}
return -1;
}

Correct approach:

int FindFirst(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 the first found match in binary search is always the first occurrence.

#2 Using binary search on an unsorted array.

Wrong approach:

int FindLast(int[] arr, int target) {
int low = 0, high = arr.Length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
} // array is unsorted, so result is unreliable

Correct approach:

Use linear search for unsorted arrays:
int FindLastUnsorted(int[] arr, int target) {
for (int i = arr.Length - 1; i >= 0; i--) {
if (arr[i] == target) return i;
}
return -1;
}

Root cause:

Assuming binary search works without sorted data.

#3 Not handling empty arrays or arrays without the target element.

Wrong approach:

int FindFirst(int[] arr, int target) {
int low = 0, high = arr.Length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
// no return for not found case
}

Correct approach:

int FindFirst(int[] arr, int target) {
int low = 0, high = arr.Length - 1, result = -1;
while (low <= high) {
int mid = (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 default value when the element is not found.

Key Takeaways

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

Linear search is simple but inefficient for large data; binary search leverages sorted order to find occurrences quickly.

Binary search for boundaries requires careful adjustment to continue searching after a match to find exact first or last positions.

Handling edge cases like empty arrays, missing elements, and unsorted data is crucial for robust implementations.

Understanding these concepts improves searching skills and prepares learners for advanced data structure queries.

Practice

1. What does the "First and Last Occurrence of Element" problem ask you to find in an array?

easy

A. The number of unique elements in the array

B. The sum of all elements in the array

C. The maximum and minimum elements in the array

D. The first and last positions where a given element appears

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the first and last positions of a specific element in an array.

2. Step 2: Differentiate from other array queries

   It is not about sums, max/min, or counting unique elements, but about positions of a target element.

3. Final Answer:

   The first and last positions where a given element appears -> Option D

4. Quick Check:

   Positions of element = first and last occurrence [OK]

Hint: Look for positions of target element, not values or counts [OK]

Common Mistakes:

• Confusing with finding max or min element
• Trying to sum elements instead of finding positions
• Counting unique elements instead of occurrences

2. Which of the following C# code snippets correctly initializes an array to find the first and last occurrence of an element?

easy

A. int arr = {1, 2, 3, 4, 5};

B. int arr = new int[5] {1, 2, 3, 4, 5};

C. int[] arr = new int[] {1, 2, 3, 4, 5};

D. int arr[] = new int[] {1, 2, 3, 4, 5};

Solution

1. Step 1: Check array initialization syntax in C#

   Correct syntax is: int[] arr = new int[] {1, 2, 3, 4, 5};

2. Step 2: Identify incorrect options

   int arr = new int[5] {1, 2, 3, 4, 5}; has wrong syntax (cannot assign array with size and initializer like that), A is missing 'new int[]', D uses C-style syntax invalid in C#.

3. Final Answer:

   int[] arr = new int[] {1, 2, 3, 4, 5}; -> Option C

4. Quick Check:

   Correct C# array syntax = int[] arr = new int[] {1, 2, 3, 4, 5}; [OK]

Hint: Use 'int[] arr = new int[] { ... }' for array initialization [OK]

Common Mistakes:

• Using C/C++ style array declarations
• Omitting 'new int[]' keyword
• Assigning array size with initializer incorrectly

3. What will be the output of the following C# code?

int[] arr = {5, 3, 7, 3, 9};
int target = 3;
int first = -1, last = -1;
for (int i = 0; i < arr.Length; i++) {
  if (arr[i] == target) {
    if (first == -1) first = i;
    last = i;
  }
}
Console.WriteLine($"{first} {last}");

medium

A. 3 1

B. 1 3

C. 0 4

D. -1 -1

Solution

1. Step 1: Trace the loop to find first and last occurrence of 3

   Array: [5, 3, 7, 3, 9]. Target = 3. Indices: 0 to 4.
   i=0: arr[0]=5 !=3 skip
   i=1: arr[1]=3 == target, first=-1 so first=1, last=1
   i=2: arr[2]=7 !=3 skip
   i=3: arr[3]=3 == target, first=1 (unchanged), last=3
   i=4: arr[4]=9 !=3 skip

2. Step 2: Print first and last

   first=1, last=3

3. Final Answer:

   1 3 -> Option B

4. Quick Check:

   First and last index of 3 = 1 and 3 [OK]

Hint: Track first when found, update last every time [OK]

Common Mistakes:

• Swapping first and last indices
• Not updating last occurrence correctly
• Initializing first and last with wrong values

4. Identify the error in the following code that tries to find the first and last occurrence of an element:

int[] arr = {2, 4, 2, 5, 2};
int target = 2;
int first = 0, last = 0;
for (int i = 0; i < arr.Length; i++) {
  if (arr[i] == target) {
    first = i;
    last = i;
  }
}
Console.WriteLine($"{first} {last}");

medium

A. first and last are initialized incorrectly, causing wrong output

B. Loop condition should be i <= arr.Length

C. Target value is not assigned properly

D. Console.WriteLine syntax is incorrect

Solution

1. Step 1: Analyze initialization of first and last

   Both first and last start at 0. Inside loop, first and last are set to i every time target is found, so first will be overwritten and end up as last occurrence index.

2. Step 2: Identify correct approach

   First should be set only once when first occurrence is found (e.g., if first == -1). Last should update every time target is found.

3. Final Answer:

   first and last are initialized incorrectly, causing wrong output -> Option A

4. Quick Check:

   Initialize first to -1 and update only once [OK]

Hint: Initialize first to -1 and update only once [OK]

Common Mistakes:

• Overwriting first occurrence index
• Using wrong loop boundary
• Incorrect Console.WriteLine format

5. Given a sorted array with possible duplicates, how can you efficiently find the first and last occurrence of a target element using C#?

hard

A. Use two binary searches: one for first occurrence, one for last occurrence

B. Traverse the array twice: once from start, once from end

C. Use a dictionary to store element counts

D. Sort the array again and find the target

Solution

1. Step 1: Understand the array is sorted with duplicates

   Sorted array allows binary search to find positions efficiently.

2. Step 2: Use binary search twice

   One binary search finds the first occurrence by moving left when target found, another finds last occurrence by moving right.

3. Step 3: Avoid full traversal or extra sorting

   Traversing twice or sorting again is inefficient. Dictionary counts do not give positions.

4. Final Answer:

   Use two binary searches: one for first occurrence, one for last occurrence -> Option A

5. Quick Check:

   Binary search twice = efficient first and last occurrence [OK]

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

Common Mistakes:

• Using linear search on large sorted arrays
• Sorting array again unnecessarily
• Using dictionary counts instead of positions