Log inSign up
easyGeeksforGeeksNot Started

Last Occurrence of an Element

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Binary Search
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a sorted array of integers arr (which may contain duplicate elements) and a target integer target, find the last (rightmost) index of target.

If target is not found in arr, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1 · Multiple Duplicates in Array:

Input: arr = [1, 3, 5, 5, 5, 5, 67, 123, 125], target = 5
Output: 5
Explanation: 5 appears from index 2 to 5; the last occurrence is at index 5.

Example 2 · Target Absent from Array:

Input: arr = [1, 3, 5, 5, 5, 5, 67, 123, 125], target = 10
Output: -1
Explanation: 10 does not exist in arr, so return -1.

Example 3 · All Elements Identical:

Input: arr = [7, 7, 7, 7], target = 7
Output: 3
Explanation: The last occurrence of 7 is at the last index 3.

Constraints:

  • 1 <= arr.length <= 105
  • -109 <= arr[i] <= 109
  • arr is sorted in non-decreasing (ascending) order.
  • -109 <= target <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the right-continuation binary search branch (low = mid + 1 on match).
  • Understand the relationship between upper_bound - 1 and Last Occurrence.
  • Formulate robust range searches across duplicate-dense arrays.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sorted array containing duplicate elements
  • Find rightmost / last index of target value
  • Subproblem for counting frequency in sorted array

Algorithmic Decision Tree:

  • Initialize low = 0, high = n - 1, ans = -1.
  • If arr[mid] == target: ans = mid, low = mid + 1 (continue searching right).
  • If arr[mid] < target: low = mid + 1 (search right).
  • If arr[mid] > target: high = mid - 1 (search left).
  • Return ans.

Connected Patterns:

First Occurrence of an ElementUpper BoundCount OccurrencesFind First and Last Position

1. Linear Scan from Right

Intuition

Iterate backwards from n - 1 down to 0. The first element equal to target is the rightmost occurrence. If loop completes, return -1.

When to apply: Unsorted collections or very small arrays.

Algorithm

  1. Step 1: Iterate index i from arr.length - 1 down to 0.
  2. Step 2: If arr[i] == target, return index i immediately.
  3. Step 3: If loop finishes without match, return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int lastOccurrence(const vector<int>& arr, int target) {
7 for (int i = (int)arr.size() - 1; i >= 0; i--) {
8 if (arr[i] == target) return i;
9 }
10 return -1;
11}
12
13int main() {
14 vector<int> arr = {1, 3, 5, 5, 5, 5, 67, 123, 125};
15 cout << "Linear Last Occurrence of 5: " << lastOccurrence(arr, 5) << endl;
16 return 0;
17}

Time & Space Complexity

  • Time complexity: O(N) — Worst case checks all N elements when target is at index 0 or absent.
  • Space complexity: O(1) — Uses a single loop index variable.

2. Upper Bound Derivation

Intuition

Find ub = upper_bound(arr, target). The element at ub - 1 is the candidate for the last occurrence. If ub > 0 && arr[ub - 1] == target, return ub - 1. Else return -1.

When to apply: When Upper Bound utility function is readily available.

Algorithm

  1. Step 1: Compute upper_bound index ub (smallest index with arr[i] > target).
  2. Step 2: Check if ub > 0 and arr[ub - 1] == target.
  3. Step 3: If valid, return ub - 1.
  4. Step 4: Else return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int lastOccurrence(const vector<int>& arr, int target) {
8 auto it = upper_bound(arr.begin(), arr.end(), target);
9 int ub = distance(arr.begin(), it);
10 if (ub > 0 && arr[ub - 1] == target) {
11 return ub - 1;
12 }
13 return -1;
14}
15
16int main() {
17 vector<int> arr = {1, 3, 5, 5, 5, 5, 67, 123, 125};
18 cout << "Upper Bound Last Occurrence: " << lastOccurrence(arr, 5) << endl;
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(log N) — Upper bound binary search executes in O(log N) iterations.
  • Space complexity: O(1) — Uses constant auxiliary memory.

3. Direct Binary Search with Right Continuation (Gold Standard)

Intuition

Initialize ans = -1, low = 0, high = n - 1. While low <= high: calculate mid. If arr[mid] == target, record ans = mid and move right low = mid + 1. If arr[mid] < target, move right low = mid + 1. If arr[mid] > target, move left high = mid - 1. Return ans.

When to apply: Industry standard optimal solution for last occurrence in sorted arrays.

Algorithm

  1. Step 1: Initialize low = 0, high = arr.length - 1, and ans = -1.
  2. Step 2: While low <= high, compute mid = low + (high - low) / 2.
  3. Step 3: If arr[mid] == target: update ans = mid and search right (low = mid + 1).
  4. Step 4: Else if arr[mid] < target: search right (low = mid + 1).
  5. Step 5: Else (arr[mid] > target): search left (high = mid - 1).
  6. Step 6: Return ans.

Last Occurrence Search Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Initialize low = 0, high = 8, ans = -1
Visual state
Values and pointers at this exact step
array
S
1
3
5
5
5
5
67
123
125
0
↑ low
1
2
3
4
↑ mid
5
6
7
8
↑ high
Variables at this step
low
0
high
8
mid
4
midVal
5
ans
4
Check / comparison
arr[mid] = 5 == target = 5 -> MATCH!
Decision / next transition
Record ans = 4. Search right for later duplicates: low = mid + 1 = 5.
Why this step matters

Initialize low = 0, high = 8, ans = -1. Calculate mid = 0 + (8 - 0) / 2 = 4. arr[4] = 5.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int lastOccurrence(const vector<int>& arr, int target) {
7 int low = 0, high = (int)arr.size() - 1;
8 int ans = -1;
9
10 while (low <= high) {
11 int mid = low + (high - low) / 2;
12
13 if (arr[mid] == target) {
14 ans = mid; // Candidate found, search right for later duplicates
15 low = mid + 1;
16 } else if (arr[mid] < target) {
17 low = mid + 1;
18 } else {
19 high = mid - 1;
20 }
21 }
22 return ans;
23}
24
25int main() {
26 vector<int> arr = {1, 3, 5, 5, 5, 5, 67, 123, 125};
27 int target = 5;
28 cout << "Last Occurrence of " << target << " is at index: " << lastOccurrence(arr, target) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(log N) — Halves search interval each step in log2(N) iterations.
  • Space complexity: O(1) — Uses constant O(1) auxiliary pointer variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Scan from RightO(N)O(1)Scan backwards from index n - 1 until first match.Linear backward scan
2.Upper Bound DerivationO(log N)O(1)Use upper_bound and check index ub - 1.None
3.Direct Binary Search Right ContinuationOptimalO(log N)O(1)Direct binary search setting low = mid + 1 on target match.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Searching left on match instead of searching right.

Pitfall 2:

Returning mid immediately upon match.

Crucial Edge Cases to Validate:

  • Target Absent: arr = [1, 2, 3], target = 4 -> returns -1.
  • All Elements Equal to Target: arr = [5, 5, 5, 5], target = 5 -> returns index 3 (last index).
  • Single Element Array: arr = [10], target = 10 -> returns 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight how First Occurrence + Last Occurrence solve 'Count Occurrences in Sorted Array' in 2 * log N time.
  2. Explain how upper_bound - 1 provides an alternative one-liner solution in C++.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we set low = mid + 1 when arr[mid] == target in Last Occurrence search?

2.What is the formula to calculate the total count of occurrences of x using First and Last occurrence indices?

Back to DSA Sheet