The question can be solved pretty easily in linear time but solving it in O(logn) time is the real trick here. As soon as you see a question asking for O(logn) complexity, the first thing which should come to mind is binary search. We’ll implement Binary Search here as well.
Binary search approach:
Let’s say we are at the middle index (mid) b/w the two bounds l (left) and r (right), i.e. mid = l+(r-l)/2 [to prevent overflow]. Now, consider when nums[mid] = nums[mid-1]:
1 1 2 2 3 4 4
^ ^ ^
l mid r
Now, as nums[mid] = nums[mid-1] and the number of elements b/w l and mid (inclusive) are *even* so that means that the single element cannot lie to the left of mid. So we do `l = mid+1`.
1 1 2 3 3 4 4 8 8
^ ^ ^
l mid r
Here, as nums[mid] = nums[mid-1] and the number of elements b/w l and mid (inclusive) are *odd* so that means that the single element *will* lie to the left of mid. So we do `r = mid-2`.
Similarly, when nums[mid] = nums[mid+1]:
1 1 2 3 3 4 4
^ ^ ^
l mid r
Now, as nums[mid] = nums[mid+1] and the number of elements b/w mid and r (inclusive) are *even* so that means that the single element cannot lie to the right of mid. So we do `r = mid-1`.
1 1 3 3 2
^ ^ ^
l mid r
Now, as nums[mid] = nums[mid+1] and the number of elements b/w mid and r (inclusive) are *odd* so that means that the single element *will* lie to the right of mid. So we do `l = mid+2`.
Code:
int singleNonDuplicate(vector<int>& nums) {
int l = 0, r = nums.size()-1, mid;
while (l<r) {
mid = l+(r-l)/2;
if (nums[mid]==nums[mid+1]) {
if ((r-mid)%2==0)
l=mid+2;
else
r=mid-1;
continue;
}
if (nums[mid]==nums[mid-1]) {
if ((mid-l)%2==0)
r=mid-2;
else
l=mid+1;
continue;
}
return nums[mid];
}
return nums[l];
}
Time complexity: O(logn) Space complexity: O(1)
Same approach, shorter code
Solution by @baguette
public static int singleNonDuplicate(int[] nums) {
int start = 0, end = nums.length - 1;
while (start < end) {
// We want the first element of the middle pair,
// which should be at an even index if the left part is sorted.
// Example:
// Index: 0 1 2 3 4 5 6
// Array: 1 1 3 3 4 8 8
// ^
int mid = (start + end) / 2;
if (mid % 2 == 1) mid--;
// We didn't find a pair. The single element must be on the left.
// (pipes mean start & end)
// Example: |0 1 1 3 3 6 6|
// ^ ^
// Next: |0 1 1|3 3 6 6
if (nums[mid] != nums[mid + 1]) end = mid;
// We found a pair. The single element must be on the right.
// Example: |1 1 3 3 5 6 6|
// ^ ^
// Next: 1 1 3 3|5 6 6|
else start = mid + 2;
}
// 'start' should always be at the beginning of a pair.
// When 'start > end', start must be the single element.
return nums[start];
}