LeetCode 540: Single Element in a Sorted Array

Problem Restatement

We are given a sorted integer array nums.

Every element appears exactly twice, except one element that appears exactly once.

We need to return the single element.

The required solution must run in:

O(log n)

time and:

O(1)

space.

The sorted order is the key. Since equal values appear next to each other, every duplicated value forms an adjacent pair.

The official statement requires returning the element that appears only once, with every other element appearing exactly twice. The solution must use logarithmic time and constant space.

Input and Output

Function shape:

def singleNonDuplicate(nums: list[int]) -> int:
    ...

Examples

Consider:

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

Every number appears twice except:

2

So the answer is:

2

Another example:

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

The single element is:

10

So the answer is:

10

First Thought: Linear Scan

Because the array is sorted, duplicates are adjacent.

So one simple method is to scan the array in steps of two:

nums[0] with nums[1]
nums[2] with nums[3]
nums[4] with nums[5]

When we find a pair that does not match, the first element of that pair is the single element.

Example:

[1, 1, 2, 3, 3]

Compare:

nums[0] == nums[1]

Then compare:

nums[2] != nums[3]

So nums[2] is the single element.

This works, but it takes O(n) time. The problem asks for O(log n), so we need binary search.

Key Insight

Before the single element, pairs start at even indices.

After the single element, pairs start at odd indices.

Example:

[1, 1, 2, 3, 3, 4, 4]

Before the single element 2:

index 0, 1 -> pair 1, 1

The pair starts at even index 0.

After the single element:

index 3, 4 -> pair 3, 3
index 5, 6 -> pair 4, 4

The pairs start at odd indices.

So we can use index parity to decide which half contains the single element.

A clean way is to force mid to be even.

Then compare:

nums[mid] == nums[mid + 1]

If they are equal, then the pair at mid, mid + 1 is valid. The single element must be after this pair.

If they are not equal, then the pairing is broken at or before mid. The single element is at mid or to the left.

Algorithm

Use binary search with two pointers:

left = 0
right = len(nums) - 1

While left < right:

1. Compute mid.
2. If mid is odd, subtract 1 so that mid is even.
3. Compare nums[mid] and nums[mid + 1].
4. If they are equal, move rightward:

left = mid + 2

5. Otherwise, keep the left half:

right = mid

When the loop ends, left == right.

That index is the single element.

Correctness

The array consists of adjacent duplicate pairs and one single element.

Before the single element, the duplicate pairs occupy indices:

(0, 1), (2, 3), (4, 5), ...

So each pair starts at an even index.

After the single element, the single element shifts the pairing by one position. Therefore, duplicate pairs start at odd indices.

During binary search, the algorithm always chooses an even mid.

If nums[mid] == nums[mid + 1], then the pair beginning at mid is correctly aligned. That means the single element cannot be at or before mid + 1; otherwise this pair alignment would already be broken. So the algorithm safely discards the range through mid + 1.

If nums[mid] != nums[mid + 1], then the pair starting at mid is not correctly aligned. This means the single element is either exactly at mid or lies before it. So the algorithm safely keeps the range ending at mid.

Each step preserves the invariant that the single element lies inside [left, right].

When left == right, only one candidate remains. By the invariant, that candidate is the single element.

Complexity

Let n = len(nums).

Implementation

class Solution:
    def singleNonDuplicate(self, nums: list[int]) -> int:
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = (left + right) // 2

            if mid % 2 == 1:
                mid -= 1

            if nums[mid] == nums[mid + 1]:
                left = mid + 2
            else:
                right = mid

        return nums[left]

Code Explanation

We start with the whole array:

left = 0
right = len(nums) - 1

The loop continues while more than one candidate remains:

while left < right:

We compute the middle index:

mid = (left + right) // 2

Then we force mid to be even:

if mid % 2 == 1:
    mid -= 1

This lets us always compare a potential pair:

nums[mid], nums[mid + 1]

If the pair is valid:

if nums[mid] == nums[mid + 1]:

then the single element must be after it:

left = mid + 2

Otherwise, the pairing has already broken:

right = mid

At the end:

return nums[left]

left points to the only remaining candidate.

Alternative: XOR Trick

There is a clever linear-time solution using XOR.

class Solution:
    def singleNonDuplicate(self, nums: list[int]) -> int:
        answer = 0

        for num in nums:
            answer ^= num

        return answer

This works because:

x ^ x == 0

and:

x ^ 0 == x

So all duplicated numbers cancel out.

However, this solution takes O(n) time, so it does not satisfy the problem’s required O(log n) time.

Testing

def run_tests():
    s = Solution()

    assert s.singleNonDuplicate([1, 1, 2, 3, 3, 4, 4, 8, 8]) == 2
    assert s.singleNonDuplicate([3, 3, 7, 7, 10, 11, 11]) == 10
    assert s.singleNonDuplicate([1]) == 1
    assert s.singleNonDuplicate([1, 2, 2, 3, 3]) == 1
    assert s.singleNonDuplicate([1, 1, 2, 2, 3]) == 3

    print("all tests passed")

run_tests()