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

Recall & Review

beginner

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

It means 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 the position (index) where a given element appears for the very last time when we look from the end of the array.

intermediate

Why is binary search useful for finding first and last occurrences in a sorted array?

Because binary search quickly narrows down the search area by dividing the array in half repeatedly, making it efficient to find the exact first or last position of an element.

beginner

In a linear search for first occurrence, what is the worst-case time complexity?

O(n), where n is the number of elements in the array, because you may need to check every element until you find the first occurrence.

intermediate

How can you modify binary search to find the last occurrence of an element?

After finding the element, continue searching in the right half to check if the element appears later, updating the last occurrence index until no more are found.

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 if it matches, move left to find earlier occurrences

B Check the last element first

C Start from the beginning and move right

D Check the middle element and if it matches, move right to find later occurrences

In binary search for first occurrence, when you find the element, you continue searching to the left to find if it appears earlier.

If an element does not exist in the array, what should the function return when searching for first or last occurrence?

A The index 0

B The length of the array

C -1 or a value indicating not found

D The middle index

Returning -1 or a similar value indicates the element is not found in the array.

What is the time complexity of finding first and last occurrence using binary search in a sorted array?

A O(log n)

B O(n)

C O(n log n)

D O(1)

Binary search runs in O(log n) time, making it efficient for this task.

Which of these is NOT a correct approach to find first occurrence of an element?

A Linear search from start to end

B Using a hash map to store indices

C Binary search with left side exploration

D Binary search with right side exploration

Binary search with right side exploration is used for last occurrence, not first.

If the array is unsorted, what is the best way to find first and last occurrence?

A Binary search

B Linear search

C Sorting then binary search

D Hashing

Binary search requires sorted arrays. For unsorted arrays, linear search is the direct method.

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 after finding the element.

Describe the difference between finding first and last occurrence of an element in a sorted array.

Focus on which side of the array to continue searching after finding the element.

Practice

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

easy

A. The maximum and minimum elements in the array

B. The sum of all elements in the array

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

D. The number of unique elements in the array

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: Identify what is required

   We need to locate the earliest and latest index where the element appears.

3. Final Answer:

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

4. Quick Check:

   First and last occurrence = positions of element [OK]

Hint: Look for earliest and latest index of element [OK]

Common Mistakes:

• Confusing with sum or max/min of array
• Returning count instead of positions
• Ignoring if element is not present

2. Which of the following C++ code snippets correctly finds the first occurrence of element x in vector arr?

easy

A. int first = 0; while(arr[first] != x) { first++; }

B. int first = -1; for(int i=0; i

C. int first = arr.size(); for(int i=0; i

D. int first = -1; for(int i=arr.size()-1; i>=0; i--) { if(arr[i] == x) { first = i; break; } }

Solution

1. Step 1: Check each option for correctness

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

2. Step 2: Identify errors in other options

   int first = 0; while(arr[first] != x) { first++; } may cause out-of-bound error if x not found; int first = arr.size(); for(int i=0; i=0; i--) { if(arr[i] == x) { first = i; break; } } finds last occurrence due to reverse loop.

3. Final Answer:

   int first = -1; for(int i=0; i -> Option B

4. Quick Check:

   Loop from start, break on first match = first occurrence [OK]

Hint: Loop forward, break on first match for first occurrence [OK]

Common Mistakes:

• Looping backward for first occurrence
• Not handling element not found case
• Using wrong initial index values

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

std::vector<int> arr = {2, 3, 5, 3, 7};
int x = 3;
int first = -1, last = -1;
for(int i=0; i<arr.size(); i++) {
  if(arr[i] == x) {
    if(first == -1) first = i;
    last = i;
  }
}
std::cout << first << " " << last << std::endl;

medium

A. 2 3

B. 0 4

C. 1 1

D. 1 3

Solution

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

   Indices: 0->2, 1->3, 2->5, 3->3, 4->7. First 3 at index 1, last 3 at index 3.

2. Step 2: Confirm output printed

   Prints first and last indices: 1 3.

3. Final Answer:

   1 3 -> Option D

4. Quick Check:

   First=1, Last=3 for element 3 [OK]

Hint: Track first set once, update last on every match [OK]

Common Mistakes:

• Confusing indices with values
• Not updating last occurrence correctly
• Printing values instead of indices

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

int last = -1;
for(int i=0; i<arr.size(); i++) {
  if(arr[i] = x) {
    last = i;
  }
}

medium

A. Using assignment (=) instead of comparison (==) in if condition

B. Loop should run backwards from end to start

C. Variable last should be initialized to 0

D. Missing break statement after finding last occurrence

Solution

1. Step 1: Check the if condition

   The condition uses single '=' which assigns x to arr[i], not compares.

2. Step 2: Understand impact of assignment in condition

   Assignment returns value of x, which may cause wrong behavior or infinite loop.

3. Final Answer:

   Using assignment (=) instead of comparison (==) in if condition -> Option A

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Use '==' for comparison, '=' is assignment [OK]

Common Mistakes:

• Confusing '=' and '==' in conditions
• Thinking loop direction causes bug here
• Assuming break needed for last occurrence

5. Given a sorted vector arr and an element x, which approach is the most efficient to find the first and last occurrence of x?

hard

A. Use binary search twice to find first and last positions

B. Use linear search from start to end

C. Sort the array again and then find occurrences

D. Use a hash map to store all indices of elements

Solution

1. Step 1: Understand the array is sorted

   Sorted array allows binary search to find elements efficiently.

2. Step 2: Use binary search twice

   One binary search finds first occurrence, another finds last occurrence in O(log n) time.

3. Step 3: Compare other options

   Linear search is O(n), sorting again is unnecessary, hash map adds extra space and complexity.

4. Final Answer:

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

5. Quick Check:

   Sorted array + binary search = efficient first/last occurrence [OK]

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

Common Mistakes:

• Using linear search on sorted array
• Sorting array again unnecessarily
• Ignoring binary search advantages