[Python] 3 Simple Approaches with Explanation
Approach 1: (Optimised) Brute Force\n\nThere are a few ways to brute force a solution. One way is to count the number of times each element appears in the array
### Approach 1: (Optimised) Brute Force\n\nThere are a few ways to brute force a solution. One way is to count the number of times each element appears in the array, and then return the value with a counter of 1.\n\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums: List[int]) -> int:\n        counts = defaultdict(int)\n        for num in nums:\n            counts[num] += 1\n        for num, count in counts.items():\n            if count == 1:\n                return num\n        return -1  # this will never be reached\n\t\t# return Counter(nums).most_common()[-1][0]  # one-liner, but TC O(nlogn)\n```\n\n**TC: O(2n) ~ O(n)**, since we loop through the array twice.\n**SC: O(n)**, since we used a dictionary / Counter object.\n\nAnother way is to check if each element has been seen before in the array. This method is intrinsically highly optimised since we know that duplicate elements are adjacent to each other.\n\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums: List[int]) -> int:\n        val, seen = -1, True\n        for num in nums:\n            if val == num:\n                seen = True\n            elif seen:\n                val = num\n                seen = False\n            else:\n                return val\n        return -1  # this will never be reached\n```\n\n**TC: O(n)**, since we only loop through the array once.\n**SC: O(1)**, since no additional data structures are used.\n\nWe can further optimise this method by abusing the adjacency of the duplicate elements: checking elements pairwise for equality.\n\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums: List[int]) -> int:\n        for i in range(0, len(nums)-1, 2):  # pairwise comparison\n            if nums[i] != nums[i+1]:  # found the single element\n                return nums[i]\n        return nums[-1]  # the last element is the single element\n```\n\n**TC: O(<img src="http://latex.codecogs.com/png.image?\\dpi{110}&space;\\frac{n}{2}" title="\\frac{n}{2}" />) ~ O(n)**, since we loop through the array two-by-two.\n**SC: O(1)**; no additional data structures used.\n\n---\n\n### Approach 2: (One-liner) Reducing Operations\n\nSince we know that every element repeats twice except for the single element, we can try to apply a function where all duplicate elements cancel each other out, leaving only the single element.\n\nOne such operation is to take the summation of all elements, but have each element alternate between positive and negative absolute values. This guarantees that each pair of duplicate elements has one positive and one neagtive absolute value, thereby cancelling each other out when added together.\n\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums: List[int]) -> int:\n        result = 0\n        for i in range(len(nums)):\n            if i%2:  # alternate between +ve and -ve\n                result -= nums[i]\n            else:\n                result += nums[i]\n        return result\n\t\t# return sum((-1)**i*v for i,v in enumerate(nums))  # one-liner\n```\n\nAnother such operation: bitwise-XOR. Bitwise-XOR works because `a XOR 0 = a` and `a XOR a = 0` for all real numbers `a`, therefore, chaining bitwise-XORs on `nums` will cancel out all duplicates and leave us with the single element.\n\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums: List[int]) -> int:\n        result = 0\n        for num in nums:\n            result ^= num\n        return result\n        # return reduce(xor, nums)  # one-liner\n```\n\n**TC: O(n)**, since we loop through all elements in the array.\n**SC: O(1)**, as discussed previously.\n\nWe can further optimise these approaches by looping through the array pairwise as per Approach 1.\n\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums: List[int]) -> int:\n        result = nums[0]\n        for i in range(1, len(nums), 2):\n            result += nums[i+1]-nums[i]\n        return result\n\t\t# return nums[0] + sum(nums[i+1]-nums[i] for i in range(1, len(nums), 2))  # one-liner\n```\n\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums: List[int]) -> int:\n        result = nums[0]\n        for i in range(1, len(nums), 2):\n            result ^= nums[i]^nums[i+1]\n        return result\n        # return reduce(lambda x,i: x^nums[i]^nums[i+1], range(1, len(nums), 2), nums[0])  # one-liner\n```\n\n**TC: O(<img src="http://latex.codecogs.com/png.image?\\dpi{110}&space;\\frac{n}{2}" title="\\frac{n}{2}" />) ~ O(n)**, as discussed previously.\n**SC: O(1)**, as discussed previously.\n\n---\n\n### Approach 3: Binary Search\n\nSince the array is sorted and the requirement is for the TC to be O(<img src="http://latex.codecogs.com/svg.image?log(n)" title="log(n)" />), it should be clear that binary search is to be used. But what exactly is the condition to check for? Consider the following example:\n\n```text\nnums = [ 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8 ]\nfirst:   ^     ^     ^     ^  ^     ^     ^     ^\nindex:   0     2     4     6  7     9     11    13\n```\n\nIt becomes clear that the index of the first of each duplicate element shows us where the single element is: **if the index is even, the single element lies in the upper end of the search space; but if the index is odd, the single element lies in the lower end of the search space**.\n\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums: List[int]) -> int:\n        lo, hi = 0, len(nums)-1\n        while lo < hi:\n            mid = lo+(hi-lo)//2\n            if nums[mid] == nums[mid-1]:  # duplicate found\n                if mid%2:       # target > mid\n                    lo = mid+1  # exclude second index mid; mid+1\n                else:           # target < mid\n                    hi = mid-2  # exclude first index mid-1; mid-1-1\n            elif nums[mid] == nums[mid+1]:  # duplicate found\n                if mid%2:       # target < mid\n                    hi = mid-1  # exclude first index mid; mid-1\n                else:           # target > mid\n                    lo = mid+2  # exclude second index mid+1; mid+1+1\n            else:  # no duplicate found, target == mid\n                return nums[mid]\n        return nums[lo]\n```\n\nA shorter but more unintuitive way: checking pairwise at `mid` via `mid^1`. `mid^1` returns the next odd number if `mid` is even, and returns the previous even number if `mid` is odd (you can try it for yourself). By checking pairwise, if the numbers are the same, it is equivalent to the first index being even. Likewise, the numbers not being equal is equivalent to the first index being odd.\n\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums: List[int]) -> int:\n        lo, hi = 0, len(nums)-2  # hi starts from an even index so that hi^1 gives the next odd number\n        while lo <= hi:\n            mid = lo+(hi-lo)//2\n            if nums[mid] == nums[mid^1]:\n                lo = mid+1\n            else:\n                hi = mid-1\n        return nums[lo]\n```\n\n**TC: O(<img src="http://latex.codecogs.com/svg.image?log(n)" title="log(n)" />)**, classic binary search time complexity.\n**SC: O(1)**, as discussed previously.\n\n---\n\nPlease upvote if this has helped you! Appreciate any comments as well :)
['Binary Tree', 'Python', 'Python3']