First and Last Occurrence of Element in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does 'First Occurrence of Element' mean in an array?

It means finding the position (index) where a given element appears for the very first time when we look from the start of the array.

beginner

What does 'Last Occurrence of Element' mean in an array?

It means finding the position (index) where a given element appears for the very last time when we look from the start to the end of the array.

intermediate

Why is it useful to find the first and last occurrence of an element?

Knowing these positions helps us understand how many times the element appears and where it is located, which is useful in counting, searching, and range queries.

intermediate

How can binary search help in finding the first and last occurrence of an element in a sorted array?

Binary search can be modified to find the first or last occurrence by adjusting the search boundaries when the element is found, moving left to find first or right to find last occurrence.

intermediate

What is the time complexity of finding first and last occurrence using binary search?

The time complexity is O(log n) because binary search divides the search space in half each time, making it very efficient for sorted arrays.

What is the first step to find the first occurrence of an element in a sorted array using binary search?

A Check the middle element and move left if element matches

B Check the middle element and move right if element matches

C Scan the array from the end

D Return the last index immediately

To find the first occurrence, when the middle element matches, we move left to check if there is an earlier occurrence.

If an element is not found in the array, what should be the output for first and last occurrence?

A Return the length of the array

B Return 0 for both

C Return -1 for both

D Return the first index

If the element is not present, returning -1 indicates it was not found.

What is the main difference between finding first and last occurrence using binary search?

A For first occurrence, move left on match; for last occurrence, move right on match

B For first occurrence, move right on match; for last occurrence, move left on match

C Both always move left on match

D Both always move right on match

To find first occurrence, we try to find an earlier match by moving left; for last occurrence, we try to find a later match by moving right.

What is the time complexity of a simple linear search to find first and last occurrence?

A O(1)

B O(n)

C O(n log n)

D O(log n)

Linear search checks each element one by one, so it takes O(n) time.

Which data structure property allows binary search to be used for finding first and last occurrence?

A Array is unsorted

B Array is empty

C Array has duplicates only

D Array is sorted

Binary search requires the array to be sorted to work correctly.

Explain how to find the first occurrence of an element in a sorted array using binary search.

Think about narrowing the search to the left side when you find the element.

Describe the difference between linear search and binary search for finding first and last occurrence.

Consider efficiency and array requirements.

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