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

Intuition

The simplest approach is to scan the array and check each element against its neighbors. If an element is different from both its left and right neighbors, it must be the single element. This works because every other element appears exactly twice and must be adjacent to its duplicate in a sorted array.

Algorithm

Iterate through the array with index i.
For each element, check if it equals its left neighbor (if exists) or right neighbor (if exists).
If the element matches neither neighbor, return it as the single element.

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)

Intuition

XOR has a useful property: a number XORed with itself gives 0, and a number XORed with 0 gives the number itself. Since every element except one appears twice, XORing all elements together will cancel out all pairs, leaving only the single element.

Algorithm

Initialize a variable xorr to 0.
XOR every element in the array with xorr.
Return xorr, which now holds the single non-duplicate element.

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

Intuition

Since the array is sorted and every element except one appears twice, we can use binary search. Before the single element, pairs start at even indices (0, 2, 4...). After the single element, this pattern shifts. By checking whether the middle element pairs correctly with its neighbor, we can determine which half contains the single element.

Algorithm

Initialize two pointers l and r at the start and end of the array.
While l <= r:
- Compute the middle index m.
- If nums[m] differs from both neighbors, return nums[m].
- Calculate the size of the left portion (excluding the pair containing m).
- If the left size is odd, the single element is on the left; move r to m - 1.
- Otherwise, the single element is on the right; move l to m + 1.
Return the found element.

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

Intuition

We can simplify binary search by only considering even indices. In a valid array without the single element disruption, every pair starts at an even index, so nums[even] == nums[even + 1]. If this condition holds at the middle even index, the single element must be to the right. Otherwise, it is on the left or at the current position.

Algorithm

Initialize l = 0 and r = n - 1.
While l < r:
- Compute the middle index m. If m is odd, decrement it to make it even.
- If nums[m] != nums[m + 1], the single element is at or before m; set r = m.
- Otherwise, the single element is after m; set l = m + 2.
Return nums[l].

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

Intuition

We can use XOR with 1 to elegantly find the pair index. For even indices, m ^ 1 gives m + 1; for odd indices, it gives m - 1. This means nums[m] should equal nums[m ^ 1] if we are in the portion before the single element. If they differ, the single element is at or before index m.

Algorithm

Initialize l = 0 and r = n - 1.
While l < r:
- Compute the middle index m.
- If nums[m] != nums[m ^ 1], the single element is at or before m; set r = m.
- Otherwise, the single element is after m; set l = m + 1.
Return nums[l].

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)$

Common Pitfalls

Forgetting the Array is Sorted

Many candidates jump straight to the XOR solution without recognizing that the sorted property enables an $O(\log n)$ binary search approach. While XOR works correctly, it only achieves $O(n)$ time complexity and fails to leverage the key constraint that makes this problem unique.

Incorrect Index Parity Logic

The binary search solution relies on understanding that before the single element, pairs start at even indices (index 0, 2, 4...) and after it, this pattern shifts. A common mistake is getting the parity check backwards or not properly handling whether to compare with the left or right neighbor based on the current index.

Off-by-One Errors in Boundary Checks

When checking neighbors at m-1 or m+1, failing to validate bounds can cause array index out-of-bounds errors. This is especially problematic at the edges of the array where the single element might be the first or last element.