540. Single Element in a Sorted Array - Explanation

Description

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]

Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]

Output: 10

Constraints:

1 <= nums.length <= 1,00,000.
0 <= nums[i] <= 1,00,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if ((i and nums[i] == nums[i - 1]) or
                (i < n - 1 and nums[i] == nums[i + 1])
            ):
                continue
            return nums[i]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

2. Brute Force (Bitwise Xor)

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

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

3. Binary Search

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            m = l + ((r - l) // 2)
            if ((m - 1 < 0 or nums[m - 1] != nums[m]) and
                (m + 1 == len(nums) or nums[m] != nums[m + 1])):
                return nums[m]

            leftSize = m - 1 if nums[m - 1] == nums[m] else m
            if leftSize % 2:
                r = m - 1
            else:
                l = m + 1

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

4. Binary Search On Even Indexes

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l < r:
            m = l + (r - l) // 2
            if m & 1:
                m -= 1
            if nums[m] != nums[m + 1]:
                r = m
            else:
                l = m + 2

        return nums[l]

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

5. Binary Search + Bit Manipulation

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l < r:
            m = (l + r) >> 1
            if nums[m] != nums[m ^ 1]:
                r = m
            else:
                l = m + 1

        return nums[l]

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$