#540
Single Element in a Sorted Array
Medium Pair parity
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In a sorted array every value appears twice except one. Find the single one in O(log n) time and O(1) space.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: everything is in pairs except one; find it in O(log n).
Why this works: before the single element, pairs start at even indexes; after it, at odd ones. Check the pair at an even mid.
Example: [1, 1, 2, 3, 3, 4, 4, 8, 8]
mid 4 (3) pairs with index 5? (4) no → hi 4mid 2 (2) pairs with 3? (3) no → hi 2mid 0 (1) pairs with 1 ✓ → lo 2 → answer 2
✦Hints open one at a time
Before the single element, pairs start at even indexes. After it, pairs start at odd indexes.
Make mid even, then check whether nums[mid] == nums[mid + 1].
↗Approach
Keep mid even. If its pair is intact (nums[mid] == nums[mid + 1]), the single element is further right: lo = mid + 2. Otherwise hi = mid.
</>Solution (Java)
class Solution {
public int singleNonDuplicate(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (mid % 2 == 1) mid--; // pairs start at even indexes
if (nums[mid] == nums[mid + 1]) lo = mid + 2;
else hi = mid;
}
return nums[lo];
}
}!Common mistake
XOR of everything — correct, but O(n), and the problem asks for O(log n).
Complexity
- Time: O(log n).
- Space: O(1).
Topic: Binary Search
🎬 Episodes 21–23: video coming soon