Find unique number in sorted array with repeats
Filed under Amazon
Free read 1 of 3Confirm that the array is sorted and that pairs are adjacent before the single element disrupts the pattern.
The question
Given a sorted array of integers where every element appears twice except for one element which appears once, find the single unique element in O(log n) time.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- Must run in O(log n) time and O(1) space.
Examples
- Input
- nums = [1,1,2,3,3,4,4,8,8]
- Output
- 2
- Why
- The number 2 appears only once.
Approach
Confirm that the array is sorted and that pairs are adjacent before the single element disrupts the pattern.
Iterate through the array or use a hash map to count frequencies, resulting in O(n) time complexity.
Use binary search by observing index pairings. Even-odd index relationships shift after the single element appears.
Handle array with only one element and unique element at boundaries.
Solution
O(log n) time, O(1) space
def singleNonDuplicate(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if mid % 2 == 1:
mid -= 1
if nums[mid] == nums[mid + 1]:
left = mid + 2
else:
right = mid
return nums[left]
Tips
- What they are testing: Test with arrays of minimum length, single elements, and unique elements at the very beginning or end.
- Common mistake: Using a linear scan which takes O(n) time instead of leveraging the sorted property with binary search.
Follow-ups
- Detailed logic for binary search
- Time and space complexity analysis
- Implementation code
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.