540. Single Element in a Sorted Array¶
Intuition¶
In a sorted array where every element appears exactly twice except one, the pairs are positioned such that:
- Before the single element, the first instance of a pair appears at even indices.
- After the single element, the first instance of a pair appears at odd indices.
By checking index parity and using binary search, we can determine which side the single element lies on and reduce our search space efficiently.
Complexity¶
| Space Complexity | Time Complexity |
|---|---|
| $\(\text{O}(1)\)$ | $\(\text{O}(\log{N})\)$ |
Code¶
public int singleNonDuplicate(int[] nums) {
int left = 0, right = nums.length - 1;
// If array has only one element
if (right == 0) return nums[0];
while (left <= right) {
int mid = (left + right) >> 1;
// Check if nums[mid] is the unique element
boolean isDifferentFromLeft = (mid - 1 < 0) || (nums[mid] != nums[mid - 1]);
boolean isDifferentFromRight = (mid + 1 >= nums.length) || (nums[mid] != nums[mid + 1]);
if (isDifferentFromLeft && isDifferentFromRight) {
return nums[mid];
}
boolean isMidIndexOdd = (mid % 2 == 1);
// Check if left side is valid (correct pairing)
if ((isMidIndexOdd && nums[mid] == nums[mid - 1]) || (!isMidIndexOdd && nums[mid] == nums[mid + 1])) {
left = mid + 1; // Unique element must be on the right
} else {
right = mid - 1; // Unique element must be on the left
}
}
return -1; // Should never reach here for a valid input
}