Sponsored
Sponsored
This approach leverages the sorted property of the array to perform a binary search, achieving a time complexity of O(log n). The key observation is that elements are paired, except for the single unique element. Thus, we can use the middle index to determine if the unique element is in the left or right half of the array based on the pairing pattern.
Time Complexity: O(log n)
Space Complexity: O(1)
1function singleNonDuplicate(nums) {
2 let left = 0, right = nums.length - 1;
3 while (left < right) {
4 let mid = Math.floor((left + right) / 2);
5 if (mid % 2 == 1) mid--;
6 if (nums[mid] === nums[mid + 1]) {
7 left = mid + 2;
8 } else {
9 right = mid;
10 }
11 }
12 return nums[left];
13}
14
15console.log(singleNonDuplicate([1, 1, 2, 3, 3, 4, 4, 8, 8]));In JavaScript, the binary search approach is used, with the 'mid' index adjusted for even index comparisons. This efficiently narrows down the location of the single element as the array is traversed.
The XOR operation cancels out all duplicates, leaving only the single unique element. This takes advantage of the property that x ^ x = 0 and x ^ 0 = x.