First and Last Occurrence of Element in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find first and last occurrence of 3 in sorted array

What is the output of the following C++ code that finds the first and last occurrence of the number 3 in a sorted array?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int firstOccurrence(const vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            high = mid - 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int lastOccurrence(const vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            low = mid + 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int main() {
    vector<int> arr = {1, 2, 3, 3, 3, 4, 5};
    int target = 3;
    cout << firstOccurrence(arr, target) << " " << lastOccurrence(arr, target) << endl;
    return 0;
}

A 1 3

B 2 4

C 3 5

D -1 -1

💡 Hint

Remember that the array is sorted and contains multiple 3s. The first occurrence is the smallest index where 3 appears, and the last occurrence is the largest index.

The first occurrence of 3 is at index 2 (0-based), and the last occurrence is at index 4. The binary search narrows down to these indices by adjusting the search space when the target is found.

❓ Predict Output

intermediate

Output when element is not present

What will be the output of the following code when searching for element 6 in the array?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int firstOccurrence(const vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            high = mid - 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int lastOccurrence(const vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            low = mid + 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int main() {
    vector<int> arr = {1, 2, 3, 3, 3, 4, 5};
    int target = 6;
    cout << firstOccurrence(arr, target) << " " << lastOccurrence(arr, target) << endl;
    return 0;
}

A -1 -1

B 0 6

C 6 6

D 5 5

💡 Hint

If the element is not found, the functions return -1.

Since 6 is not in the array, both firstOccurrence and lastOccurrence return -1, indicating the element is absent.

🔧 Debug

advanced

Identify the bug in lastOccurrence function

The following code is intended to find the last occurrence of a target in a sorted array. What is the bug causing incorrect output?

DSA C++

int lastOccurrence(const vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1, result = -1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            low = mid + 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

A The result variable is not updated when arr[mid] > target.

B The mid calculation should be 'mid = (low + high + 1) / 2'.

C The function should return 'low' instead of 'result'.

D The loop condition should be 'low <= high' instead of 'low < high'.

💡 Hint

Check the loop condition carefully to ensure all elements are checked.

Using 'low < high' causes the loop to miss checking when low equals high, potentially skipping the last occurrence. Changing to 'low <= high' ensures all elements are checked.

❓ Predict Output

advanced

Output of first and last occurrence in array with single element

What is the output of the code when the array contains only one element which is the target?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int firstOccurrence(const vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            high = mid - 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int lastOccurrence(const vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            result = mid;
            low = mid + 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int main() {
    vector<int> arr = {7};
    int target = 7;
    cout << firstOccurrence(arr, target) << " " << lastOccurrence(arr, target) << endl;
    return 0;
}

A 0 0

B -1 -1

C 0 -1

D -1 0

💡 Hint

With only one element equal to target, both first and last occurrence are at index 0.

The single element matches the target, so both first and last occurrence indices are 0.

🧠 Conceptual

expert

Why binary search is efficient for first and last occurrence?

Why is binary search preferred over linear search to find the first and last occurrence of an element in a sorted array?

A Binary search works only on unsorted arrays, so it is faster than linear search.

B Binary search can find the exact position without checking all elements, but linear search cannot find the element.

C Binary search reduces the search space by half each step, making it O(log n), while linear search is O(n).

D Binary search uses recursion which is always faster than iteration used in linear search.

💡 Hint

Think about how many elements are checked in each method.

Binary search halves the search space each time, leading to logarithmic time complexity O(log n). Linear search checks each element one by one, leading to O(n) time.

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