Find last occurrence of a number in sorted array
Filed under Amazon
Free read 3 of 3Confirm if the array contains duplicate elements and if -1 should be returned when the target is absent.
The question
Given a 0-indexed sorted array of integers nums and a target integer x, find the index of the last occurrence of x. If x is not present in nums, return -1.
Constraints
- 0 <= len(nums) <= 10^5
- -10^9 <= nums[i], x <= 10^9
- nums is sorted in non-decreasing order.
Examples
- Input
- nums = [1, 2, 2, 2, 3, 5], x = 2
- Output
- 3
- Why
- The last occurrence of target 2 is at index 3.
- Input
- nums = [1, 2, 3, 4], x = 5
- Output
- -1
- Why
- 5 is not present in nums.
Approach
Confirm if the array contains duplicate elements and if -1 should be returned when the target is absent.
Scan the sorted array from right to left to find the target's last index in O(N) time.
Perform binary search. When the target match is found at mid, record mid as the potential answer and continue searching the right half by setting left to mid + 1.
Empty array, target not present in the array, target smaller than all elements, or all elements identical.
Solution
O(log N) time, O(1) space
class Solution:
def find_last_occurrence(self, nums: list[int], x: int) -> int:
left, right = 0, len(nums) - 1
ans = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] == x:
ans = mid
left = mid + 1
elif nums[mid] < x:
left = mid + 1
else:
right = mid - 1
return ans
Tips
- What they are testing: Assesses modified binary search logic to handle duplicated elements accurately.
- Common mistake: Returning immediately upon finding any match during binary search instead of continuing to search the right half for later occurrences.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.