First and Last Occurrence of Element in DSA Python

Mental Model

Find where a number first appears and where it last appears in a list by checking each item from start to end.

Analogy: Imagine looking for a friend's name in a guest list. You note the first time you see their name and keep looking until you find the last time it appears.

Index: 0   1   2   3   4   5   6
List:  2 -> 3 -> 5 -> 3 -> 7 -> 3 -> 9
               ↑           ↑
         first occurrence  last occurrence

Dry Run Walkthrough

Input: list: [2, 3, 5, 3, 7, 3, 9], element: 3

Goal: Find the first and last positions where 3 appears in the list

Step 1: Check element at index 0 (2), not 3

2 -> 3 -> 5 -> 3 -> 7 -> 3 -> 9
↑

Why: Start from the beginning to find first occurrence

Step 2: Check element at index 1 (3), found first occurrence

2 -> [3] -> 5 -> 3 -> 7 -> 3 -> 9
     ↑

Why: Record first occurrence index as 1

Step 3: Check element at index 2 (5), not 3

2 -> 3 -> 5 -> 3 -> 7 -> 3 -> 9
          ↑

Why: Keep searching for last occurrence

Step 4: Check element at index 3 (3), update last occurrence to 3

2 -> 3 -> 5 -> [3] -> 7 -> 3 -> 9
               ↑

Why: Found another 3, update last occurrence

Step 5: Check element at index 4 (7), not 3

2 -> 3 -> 5 -> 3 -> 7 -> 3 -> 9
                    ↑

Why: Continue searching

Step 6: Check element at index 5 (3), update last occurrence to 5

2 -> 3 -> 5 -> 3 -> 7 -> [3] -> 9
                         ↑

Why: Found last occurrence so far

Step 7: Check element at index 6 (9), not 3

2 -> 3 -> 5 -> 3 -> 7 -> 3 -> 9
                              ↑

Why: End of list reached

Result:

2 -> 3 -> 5 -> 3 -> 7 -> 3 -> 9
First occurrence index: 1
Last occurrence index: 5

Annotated Code

DSA Python

class Solution:
    def first_and_last_occurrence(self, arr: list[int], x: int) -> tuple[int, int]:
        first = -1
        last = -1
        for i, val in enumerate(arr):
            if val == x:
                if first == -1:
                    first = i  # record first occurrence
                last = i       # update last occurrence
        return first, last

if __name__ == '__main__':
    arr = [2, 3, 5, 3, 7, 3, 9]
    x = 3
    sol = Solution()
    first, last = sol.first_and_last_occurrence(arr, x)
    print(f"First occurrence index: {first}")
    print(f"Last occurrence index: {last}")

for i, val in enumerate(arr):

iterate over each element with its index

if val == x:

check if current element matches target

if first == -1:

if first occurrence not set, set it now

first = i # record first occurrence

store index of first found element

last = i # update last occurrence

update last occurrence index each time element found

Output

First occurrence index: 1

Last occurrence index: 5

Complexity Analysis

Time: O(n) because we check each element once to find first and last occurrences

Space: O(1) because we only store two indices regardless of input size

vs Alternative: Better than searching twice (once for first, once for last) which would be O(2n); this does both in one pass

Edge Cases

Empty list

Returns (-1, -1) indicating element not found

DSA Python

for i, val in enumerate(arr):

Element not in list

Returns (-1, -1) indicating element not found

DSA Python

if val == x:

Element appears once

First and last occurrence indices are the same

DSA Python

last = i       # update last occurrence

When to Use This Pattern

When asked to find positions of an element's first and last appearance in a list, use a single pass scan updating indices to efficiently find both.

Common Mistakes

Mistake: Searching for first and last occurrences separately, causing extra passes
Fix: Combine both searches in one loop by updating last occurrence each time and setting first only once

Summary

Finds the first and last positions of a given element in a list.

Use when you need to know where an element starts and ends in a sequence.

Remember to scan once, set first occurrence once, and update last occurrence every time you find the element.

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