You are given a sorted array in which every value appears exactly twice, except for one value that appears only once. Return that single value. Your solution must run in O(log n) time and O(1) extra space.
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^5
- `nums` is sorted and has odd length
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
XOR of everything, or a linear scan for the element that differs from both neighbours, both cost O(n). Look at the indices instead. Left of the single element, pairs sit at (0,1), (2,3), ..., so each pair starts at an even index. The single element shifts everything after it by one, so on the right each pair starts at an odd index. If we only look at even mid values, nums[mid] == nums[mid + 1] means the pattern is still intact and the single value is further right; otherwise it is at mid or to its left.
Algorithm
- Set
lo = 0,hi = n - 1. - While
lo < hi, computemid, and ifmidis odd, subtract 1 so it is even. - If
nums[mid] == nums[mid + 1], the pair is intact:lo = mid + 2. - Otherwise the single element is at
midor before:hi = mid. - Return
nums[lo].
O(log n)Space: O(1)mid to be even is what keeps the logic simple. A neat alternative is comparing nums[mid] with nums[mid ^ 1], which pairs each even index with the next and each odd index with the previous one.class Solution: def singleNonDuplicate(self, nums: List[int]) -> int: lo, hi = 0, len(nums) - 1 while lo < hi: mid = (lo + hi) // 2 if mid % 2 == 1: mid -= 1 # look only at even indices if nums[mid] == nums[mid + 1]: lo = mid + 2 # pairs intact so far: go right else: hi = mid # single is at mid or to its left return nums[lo]