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)
1def singleNonDuplicate(nums):
2 left, right = 0, len(nums) - 1
3 while left < right:
4 mid = left + (right - left) // 2
5 if mid % 2 == 1:
6 mid -= 1
7 if nums[mid] == nums[mid + 1]:
8 left = mid + 2
9 else:
10 right = mid
11 return nums[left]
12
13print(singleNonDuplicate([1, 1, 2, 3, 3, 4, 4, 8, 8]))The Python solution applies a binary search technique, adjusting the mid index to even and comparing elements to find the transition point between pairs, which is where the single element will be located.
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.