LeetCode 540: Single Element in a Sorted Array

Bitwise

If we xor all elements in the array, the single element remains.

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        xor = 0
        for x in nums:
            xor ^= x
        
        return xor

Binary search

Since nums is sorted, all repeated numbers appear consecutively. All numbers except one has duplicates so, len(nums) is odd. Also, removing a pair of (consecutive) duplicate numbers breaks nums into two halves: one half has even length and the other half has odd length. The unique number must be in the half with odd length.

We can use binary search to find the unique number.

Time: $\mathcal{O}(\lg{n})$ , space: $\mathcal{O}(1)$ .

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        def is_unique(i):
            left_neibor = nums[i-1] if i > 0 else -1
            right_neibor = nums[i+1] if i < n-1 else -1
            return left_neibor != nums[i] and nums[i] != right_neibor

        n = len(nums)
        lo, hi = 0, n-1
        while lo <= hi:
            mid = (lo + hi) // 2
            if is_unique(mid):
                return nums[mid]

            left = mid-2 if mid-1 >= 0 and nums[mid-1] == nums[mid] else mid-1
            right = mid+2 if mid+1 < n and nums[mid] == nums[mid+1] else mid+1

            if (left+1) % 2 == 1:
                hi = left
            else:
                lo = right
        
        return None

unreasonably effective