First and Last Occurrence of Element in DSA Python - 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 do this by scanning the list or using smarter methods to find these positions quickly.

Why it matters

Without knowing the first and last occurrence, we might waste time searching the entire list repeatedly or miss important information about the element's spread. This is useful in searching, counting, and range queries, which are common in many real-world tasks like text search or data analysis.

Where it fits

Before this, you should understand arrays or lists and basic searching methods. After this, you can learn about binary search and advanced searching techniques that improve efficiency.

Mental Model

Core Idea

The first and last occurrence of an element mark the start and end positions of that element's presence in a list.

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, 3, 3, 5, 5, 5, 7, 8]
Element: 5
Positions: 0  1  2  3  4  5  6  7
           |     |  |  |  |     |
First occurrence -> position 3
Last occurrence  -> position 5

Build-Up - 6 Steps

1

Foundation

Understanding Simple Linear Search

Concept: Learn how to scan a list from start to end to find an element.

We look at each item in the list one by one from the beginning. When we find the element, we stop and note its position.

Result

We get the position of the first time the element appears.

Understanding linear search is the base for finding occurrences because it shows how to check each element step-by-step.

2

Foundation

Finding Last Occurrence by Reverse Search

Concept: Learn to scan the list from the end to find the last occurrence.

Instead of starting from the beginning, we start from the last item and move backward. When we find the element, we note its position.

Result

We get the position of the last time the element appears.

Knowing that scanning backward finds the last occurrence helps us understand the symmetry in searching.

3

Intermediate

Using Single Pass to Find Both Occurrences

🤔Before reading on: Do you think it's possible to find both first and last occurrences in one pass? Commit to yes or no.

Concept: Learn to track both first and last positions in one go by scanning once.

We scan the list once from start to end. When we find the element for the first time, we save that position as first occurrence. Every time we find the element, we update the last occurrence position.

Result

After one scan, we have both first and last occurrence positions.

Knowing that one pass can find both saves time and shows efficient use of scanning.

4

Intermediate

Binary Search for Sorted Lists

🤔Before reading on: Do you think binary search can find first and last occurrences directly? Commit to yes or no.

Concept: Use binary search to find occurrences faster in sorted lists.

Binary search splits the list repeatedly to find the element quickly. To find first occurrence, when we find the element, we continue searching left to find if it appears earlier. For last occurrence, we continue searching right.

Result

We find first and last occurrences in much fewer steps than scanning all elements.

Understanding binary search's power in sorted lists shows how to speed up searches dramatically.

5

Advanced

Implementing Binary Search for Occurrences

🤔Before reading on: Do you think the same binary search function can find both first and last occurrences with small changes? Commit to yes or no.

Concept: Modify binary search to find first or last occurrence by adjusting search boundaries.

To find first occurrence, when element is found, move search to left half to check for earlier occurrences. To find last occurrence, move search to right half after finding element. This requires careful boundary updates.

Result

Two similar binary search functions give first and last positions efficiently.

Knowing how to tweak binary search boundaries unlocks precise control over search results.

6

Expert

Handling Edge Cases and No Occurrence

🤔Before reading on: If the element is not in the list, do you think binary search returns -1 or an error? Commit to your answer.

Concept: Learn to handle cases where element is missing or appears once, ensuring robust code.

If element is not found, return -1 for both occurrences. If element appears once, first and last occurrence are the same. Carefully check boundaries to avoid infinite loops or wrong results.

Result

Robust functions that handle all cases without errors.

Understanding edge cases prevents bugs and ensures your search functions work in all situations.

Under the Hood

Binary search works by repeatedly dividing the search range in half. For first occurrence, after finding the element, it narrows the search to the left half to find earlier appearances. For last occurrence, it narrows to the right half. This uses the sorted property to skip large parts of the list quickly.

Why designed this way?

Binary search was designed to reduce search time from linear to logarithmic by exploiting sorted order. Adjusting boundaries after finding the element allows precise location of first or last occurrence without scanning all elements.

Initial array: [1, 2, 2, 2, 3, 4]
Search for 2:
┌─────────────┐
│ Left=0      │
│ Right=5     │
└─────────────┘
Find mid=2 (value=2)
For first occurrence: move Right=mid-1=1
For last occurrence: move Left=mid+1=3
Repeat until boundaries cross.

Myth Busters - 3 Common Misconceptions

Quick: Does linear search always find the last occurrence first? Commit to yes or no.

Common Belief: Linear search from start always finds the last occurrence first.

Reality: Linear search from start finds the first occurrence first, not the last.

Why it matters: Confusing this leads to wrong position results and bugs in programs relying on occurrence positions.

Quick: Can binary search be used on unsorted lists to find occurrences? Commit to yes or no.

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

Reality: Binary search only works correctly on sorted lists.

Why it matters: Using binary search on unsorted lists gives incorrect results or crashes.

Quick: Does finding the element once in binary search guarantee it's the first occurrence? Commit to yes or no.

Common Belief: Finding the element once means it's the first occurrence.

Reality: The found element may be in the middle; you must continue searching left to confirm first occurrence.

Why it matters: Assuming this causes wrong first occurrence positions and logic errors.

Expert Zone

1

Binary search for occurrences requires careful boundary updates to avoid infinite loops or missing edge positions.

2

In some languages or systems, integer overflow can happen when calculating mid as (left + right) // 2; using left + (right - left) // 2 avoids this.

3

When elements repeat many times, binary search reduces time from O(n) to O(log n), which is critical for large datasets.

When NOT to use

If the list is unsorted or very small, linear search is simpler and sometimes faster. For dynamic data where elements change often, balanced trees or hash maps might be better alternatives.

Production Patterns

In databases and search engines, binary search variants quickly find ranges of matching records. In text processing, first and last occurrence help in substring indexing and frequency analysis.

Connections

Binary Search

Builds-on

Understanding first and last occurrence deepens knowledge of binary search by showing how to adapt it for range queries.

Hash Tables

Alternative approach

Hash tables can find if an element exists quickly but do not give ordered positions, highlighting the unique value of occurrence searches in sorted data.

Signal Processing

Pattern detection

Finding first and last occurrence is like detecting start and end points of a signal pattern, showing how search concepts apply beyond computer science.

Common Pitfalls

#1 Assuming binary search returns first occurrence immediately after finding element.

Wrong approach:

def binary_search_first(arr, x):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid # Wrong: returns immediately
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1

Correct approach:

def binary_search_first(arr, x):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == x:
result = mid
right = mid - 1 # Continue searching left
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return result

Root cause:

Misunderstanding that binary search must continue after finding element to find first occurrence.

#2 Using binary search on unsorted list.

Wrong approach:

arr = [3, 1, 4, 2, 5]
# Trying binary search directly
binary_search_first(arr, 4) # Incorrect usage

Correct approach:

arr = [1, 2, 3, 4, 5] # Sorted list
binary_search_first(arr, 4) # Correct usage

Root cause:

Not recognizing binary search requires sorted data.

#3 Not handling element not found case.

Wrong approach:

def find_first(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
# Missing return if not found

Correct approach:

def find_first(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1 # Explicitly return -1 if not found

Root cause:

Forgetting to handle the case when element does not exist in the list.

Key Takeaways

First and last occurrence locate the start and end positions of an element in a list, helping understand its range.

Linear search is simple but inefficient for large or sorted lists; binary search speeds this up by dividing the search space.

Binary search must be carefully adjusted to find first or last occurrence by continuing search after finding the element.

Handling edge cases like missing elements or single occurrences is essential for robust search functions.

Knowing when to use linear search, binary search, or other data structures depends on data order and size.

Practice

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

easy

A. The total count of the element in the list

B. The last index where the element appears in the list

C. The index where the element appears first in the list

D. The element with the smallest value in the list

Solution

1. Step 1: Understand the meaning of first occurrence

   The first occurrence means the earliest position (index) where the element appears in the list when reading from left to right.

2. Step 2: Compare with other options

   Other options describe last occurrence, count, or smallest value, which are different concepts.

3. Final Answer:

   The index where the element appears first in the list -> Option C

4. Quick Check:

   First occurrence = first index [OK]

Hint: First occurrence means earliest index found [OK]

Common Mistakes:

• Confusing first occurrence with last occurrence
• Thinking it means the count of the element
• Mixing occurrence with element value

2. Which of the following Python code snippets correctly finds the first occurrence index of element 5 in list arr?

easy

A. arr.find(5)

B. arr.index(5)

C. arr.search(5)

D. arr.locate(5)

Solution

1. Step 1: Recall Python list methods

   Python lists have the method index() to find the first occurrence index of an element.

2. Step 2: Check other options

   Methods find(), search(), and locate() do not exist for Python lists.

3. Final Answer:

   arr.index(5) -> Option B

4. Quick Check:

   Use list.index(element) to find first occurrence [OK]

Hint: Use list.index() to get first occurrence index [OK]

Common Mistakes:

• Using non-existent methods like find or search on lists
• Confusing string methods with list methods
• Trying to use index without handling exceptions

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

arr = [2, 4, 5, 4, 5, 6]
first = arr.index(4)
last = len(arr) - 1 - arr[::-1].index(4)
print([first, last])

medium

A. [1, 3]

B. [3, 1]

C. [1, 4]

D. [4, 1]

Solution

1. Step 1: Find first occurrence of 4

   Using arr.index(4) returns 1 because 4 first appears at index 1.

2. Step 2: Find last occurrence of 4

   arr[::-1] reverses the list to [6, 5, 4, 5, 4, 2]. The first index of 4 in reversed list is 2. So last occurrence index = len(arr) - 1 - 2 = 6 - 1 - 2 = 3.

3. Final Answer:

   [1, 3] -> Option A

4. Quick Check:

   First = 1, Last = 3 [OK]

Hint: Reverse list and use index for last occurrence [OK]

Common Mistakes:

• Mixing up reversed index with original index
• Using last = arr.index(4) instead of reversed search
• Confusing first and last occurrence indexes

4. The following code is intended to find the first and last occurrence of element 7 in list nums. What is the error?

nums = [1, 7, 3, 7, 5]
first = nums.index(7)
last = nums.index(7, -1)
print(first, last)

medium

A. Using negative start index in index() causes ValueError

B. index() cannot find element 7 in the list

C. No error; code works correctly

D. The second index() call should use a positive start index

Solution

1. Step 1: Understand index() with start parameter

   The index() method can take a start index. Using -1 as start means start searching from the last element only.

2. Step 2: Identify the error in last occurrence search

   Using nums.index(7, -1) starts searching from index -1 (last element), so it only checks last element which is 5, not 7, causing ValueError.

3. Final Answer:

   The second index() call should use a positive start index -> Option D

4. Quick Check:

   index(start=-1) limits search to last element [OK]

Hint: Use positive start index in index() for last occurrence [OK]

Common Mistakes:

• Using negative start index in list.index()
• Expecting index() to find last occurrence without correct start
• Not handling ValueError when element not found

5. Given a sorted list data = [1, 2, 2, 2, 3, 4, 5], which approach is best to find the first and last occurrence of 2 efficiently?

hard

A. Use binary search to find first and last occurrence

B. Use linear search from start and end to find occurrences

C. Use list.index() and reversed list index() methods

D. Use count() method to find number of occurrences

Solution

1. Step 1: Understand the list is sorted

   Since the list is sorted, binary search can be used to find positions efficiently in O(log n) time.

2. Step 2: Compare approaches

   Linear search (Use linear search from start and end to find occurrences) is slower (O(n)). Using list.index() and reversed index() (Use list.index() and reversed list index() methods) is also linear. count() (Use count() method to find number of occurrences) gives count but not positions.

3. Step 3: Best approach

   Binary search can be adapted to find first and last occurrence indexes quickly.

4. Final Answer:

   Use binary search to find first and last occurrence -> Option A

5. Quick Check:

   Sorted list + binary search = efficient occurrence search [OK]

Hint: Use binary search on sorted list for fast occurrence indexes [OK]

Common Mistakes:

• Using linear search on sorted lists
• Using count() instead of finding indexes
• Not leveraging sorted property for efficiency