โ† Amazon questions

Find unique number in sorted array with repeats

Filed under Amazon

Free read 1 of 3

Confirm 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

  1. Confirm that the array is sorted and that pairs are adjacent before the single element disrupts the pattern.

Solution

O(log n) time, O(1) space

Python
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.