Find the Last Occurrence in a Sorted Array

102.4k
0

Given a sorted array of integers arr and a target value target, find the index of the last occurrence of target in the array. If the target is not present in the array, return -1.

Example 1

Input: arr = [1, 2, 4, 4, 4, 6, 8], target = 4

Output: 4

Explanation: The value 4 appears more than once, and its last appearance is at index 4.

Example 2

Input: arr = [1, 3, 5, 7, 9], target = 6

Output: -1

Explanation: The value 6 is not present in the array, so no last occurrence exists.

Brute Force Approach

The most direct idea is to scan the array and keep updating the answer whenever the target is found. Since the array is read from left to right, the latest stored matching index will naturally become the last occurrence. If the target never appears during the scan, the answer stays -1.

Algorithm

  • Start from index 0 and check each element one by one because every match may push the answer further to the right.

  • Keep a variable answer as -1 so it is easy to detect when the target was never found.

  • Whenever the current element is equal to the target, store that index in answer.

  • Continue scanning the remaining elements because another same target may appear later.

  • After the loop ends, return answer.

Dry Run

Last Occurrences Brute Dry Run

Last Occurrences Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the last index where target appears
in the sorted array.
*/
int lastOccurrence(vector<int>& arr, int target) {
// Stores the latest matching index found so far.
int answer = -1;
// Check each index from left to right.
for (int i = 0; i < (int)arr.size(); i++) {
// Update the answer whenever the target is seen again.
if (arr[i] == target) {
answer = i;
}
}
return answer;
}
};
// Driver code starts
int main() {
vector<int> arr = {1, 2, 4, 4, 4, 6, 8};
int target = 4;
Solution obj;
cout << obj.lastOccurrence(arr, target) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is length of array, because in the worst case the whole array must be scanned.

Space Complexity: O(1), because only one extra variable is used.

Optimal Approach

The useful observation is this: when arr[mid] is equal to the target, that index is valid, but it may not be the last one. Another same target may still exist on the right side. So the search should not stop immediately after finding a match. That is the core idea here. A valid match is remembered, and then the search continues toward the right to check whether a later occurrence exists. If arr[mid] is smaller than the target, the last occurrence can only be on the right side. If arr[mid] is greater than the target, the answer can only be on the left side.

Algorithm

  • Start with two pointers, low at 0 and high at the last index, because the target can lie anywhere in the array.

  • Keep a variable answer as -1. This stores the best last occurrence found so far, and it remains -1 if the target never appears.

  • Find the middle index using mid = low + (high - low) / 2 so the middle position is calculated safely.

  • If arr[mid] is equal to the target, store mid in answer. Then move low to mid + 1 because a later occurrence may still be present on the right side.

  • If arr[mid] is smaller than the target, move low to mid + 1 because every index up to mid becomes useless for the last occurrence.

  • If arr[mid] is greater than the target, move high to mid - 1 because the target, if present, must be on the left side.

  • Continue this process while low <= high.

  • Return answer at the end. If no match was found, it remains -1.

Dry Run

Last Occurrence Optimal Dry Run

Last Occurrence Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the last index where target appears
in the sorted array.
*/
int lastOccurrence(vector<int>& arr, int target) {
// Left boundary of the current search range.
int low = 0;
// Right boundary of the current search range.
int high = (int)arr.size() - 1;
// Stores the rightmost matching index found so far.
int answer = -1;
// Keep searching while a valid range still exists.
while (low <= high) {
// Calculate the middle index safely.
int mid = low + (high - low) / 2;
// A match is found, so remember it and continue on the right side.
if (arr[mid] == target) {
answer = mid;
low = mid + 1;
} else if (arr[mid] < target) {
// Values up to mid are too small, so move to the right half.
low = mid + 1;
} else {
// The current value is too large, so search only on the left side.
high = mid - 1;
}
}
return answer;
}
};
// Driver code starts
int main() {
vector<int> arr = {1, 2, 4, 4, 4, 6, 8};
int target = 4;
Solution obj;
cout << obj.lastOccurrence(arr, target) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(log2 N), N is the length of array, because the search range becomes half in each step.

Space Complexity: O(1), because only a few variables are used.

Interview follow-up Questions

Because the current match may not be the last one. Moving right helps check whether another same target appears later.

Two PointerSortingMathsGreedyBinary Search

Read Similar Blogs

MathsIntroduction to DSA

Mastering Number Basics in Programming

Input: a = 17, b = 5 Output: 2 Explanation: 17 can make three complete groups of 5, which uses 15. After that, 2 is left, so 17 % 5 = 2. Input: a = 3, b = 5 Output: 3 Explanation: 5 cannot be taken...

73.6k
MathsGreedyIntroduction to DSA

Find Remainder

Given two non-negative integers a and b , find the remainder when a is divided by b . Assume b is not 0 . Approach The small observation is very direct: the remainder is exactly what the modulo ope...

95.9k
Introduction to DSABit ManipulationMaths

Check Even or Odd

Given an integer N , determine whether it is even or odd. Return "Even" if the number is divisible by 2 , otherwise return "Odd" . Approach The first observation is the...

68.5k
Comments0