LeetCode 540 - Single Element in a Sorted Array

LeetCode Problem 540

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

The problem gives us a sorted integer array where every value appears exactly twice, except for one value that appears only once. Our task is to find that unique value.

The important detail is that the array is already sorted. Because duplicates appear next to each other in a sorted array, every repeated number forms a pair of adjacent elements. Only one number breaks this pairing pattern.

For example, in the array:

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

the numbers 1, 3, 4, and 8 all appear in adjacent pairs, while 2 appears only once.

The problem also requires that the solution run in O(log n) time and O(1) extra space. This restriction is extremely important because it rules out straightforward linear scans and hash map solutions. A linear scan would take O(n) time, which does not satisfy the logarithmic time requirement.

The constraints tell us several useful things:

• The array length can be as large as 10^5, so efficiency matters.
• The array is guaranteed to contain exactly one non-duplicate element.
• Every other element appears exactly twice.
• The array is sorted, which strongly suggests binary search.

Several edge cases are important:

• The unique element could appear at the beginning of the array.
• The unique element could appear at the end of the array.
• The array could contain only one element.
• The unique element could appear somewhere in the middle and disrupt the normal pairing structure.

A naive implementation can easily make out-of-bounds mistakes when checking neighbors, especially near the beginning or end of the array. Careful index handling is necessary.

Approaches

Brute Force Approach

A straightforward solution is to scan through the array and check elements in pairs.

Because the array is sorted and duplicates appear consecutively, we can move through the array two elements at a time. If a pair matches, we continue. If we find an element that does not match its neighbor, that element is the answer.

For example:

[1,1,2,3,3]

• Compare 1 and 1, valid pair
• Compare 2 and 3, mismatch
• Therefore 2 is the unique element

This approach is correct because every duplicated element must appear next to its pair in a sorted array. The first place where this pattern breaks identifies the single element.

However, this method requires scanning the array linearly, resulting in O(n) time complexity, which violates the problem requirement of O(log n) time.

Optimal Binary Search Approach

The key observation is that the sorted duplicate structure follows a predictable index pattern.

Before the single element appears:

• The first occurrence of each pair appears at an even index.
• The second occurrence appears at an odd index.

Example:

Index: 0 1 2 3 4 5
Value: 1 1 2 2 3 3

Notice:

• 1 starts at index 0
• 2 starts at index 2
• 3 starts at index 4

All pair starts are even.

After the single element appears, this pattern shifts:

Index: 0 1 2 3 4 5 6
Value: 1 1 2 3 3 4 4

Now:

• 3 starts at index 3
• 4 starts at index 5

The pair starting positions become odd.

This shift allows us to use binary search. By checking whether the pairing pattern is still correct at a midpoint, we can determine which side contains the single element.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Scan array sequentially and compare neighboring elements
Optimal	O(log n)	O(1)	Use binary search and index parity properties

Algorithm Walkthrough

1. Initialize two pointers, left and right, representing the current binary search range.

Initially:

left = 0
right = len(nums) - 1

2. Continue the binary search while left < right.

The search space shrinks until only one index remains. 3. Compute the midpoint:

mid = (left + right) // 2

4. Ensure mid is even.

Since pairs normally start at even indices, we want to compare a potential pair starting position.

If mid is odd, subtract one:

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

5. Compare nums[mid] with nums[mid + 1].

There are two possibilities:

• If they are equal, then all pairs up to this point are correctly aligned. The single element must be on the right side.
• If they are not equal, then the pairing structure has already been disrupted, so the single element is on the left side, including mid.

6. Update the search boundaries accordingly.

If the pair matches:

left = mid + 2

Otherwise:

right = mid

7. Eventually, left and right converge to the same index.

That index contains the single non-duplicate element. 8. Return nums[left].

Why it works

The algorithm relies on the invariant that valid pairs start at even indices before the single element appears. Once the single element is encountered, the pairing alignment shifts by one position.

By forcing mid to be even and checking whether nums[mid] equals nums[mid + 1], we can determine whether the disruption occurs before or after mid. Each iteration halves the remaining search space, guaranteeing logarithmic time complexity.

Python Solution

from typing import List

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]

The implementation begins by initializing the binary search boundaries. The loop continues until only one candidate index remains.

Inside the loop, the midpoint is calculated normally. Since valid duplicate pairs should begin at even indices, the code adjusts odd midpoint values by subtracting one. This guarantees that comparisons are always made between the expected first and second elements of a pair.

The comparison between nums[mid] and nums[mid + 1] determines whether the pairing structure remains intact.

If the pair matches, the single element must lie further to the right because everything before and including this pair is valid. Therefore, the left boundary moves forward by two positions.

If the pair does not match, the disruption has already occurred, meaning the single element lies at or before mid. The right boundary is updated accordingly.

When the loop finishes, both pointers point to the single non-duplicate element.

Go Solution

func singleNonDuplicate(nums []int) int {
    left := 0
    right := len(nums) - 1

    for left < right {
        mid := (left + right) / 2

        if mid%2 == 1 {
            mid--
        }

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

    return nums[left]
}

The Go implementation follows exactly the same logic as the Python solution. Go slices are used directly without additional memory allocation, preserving O(1) space complexity.

There are no special concerns about integer overflow because the problem constraints are small enough for standard integer arithmetic. The implementation also safely accesses nums[mid + 1] because the loop structure guarantees that mid never becomes the final index.

Worked Examples

Example 1

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

Step	left	right	mid	Adjusted mid	nums[mid]	nums[mid+1]	Action
1	0	8	4	4	3	3	Pair valid, move right
2	6	8	7	6	4	8	Pair broken, move left
3	6	6	-	-	-	-	Stop

Final answer:

nums[6] = 2

Actually, after Step 2:

• right = 6
• left = 6

So the algorithm returns:

nums[2] = 2

Correct trace:

Step	left	right	mid	Adjusted mid	nums[mid]	nums[mid+1]	Action
1	0	8	4	4	3	3	left = 6
2	6	8	7	6	4	4	left = 8
3	8	8	-	-	-	-	Stop

This trace reveals a mismatch with the expected answer, so let us trace carefully again.

Correct detailed trace:

Initial array:

Index: 0 1 2 3 4 5 6 7 8
Value: 1 1 2 3 3 4 4 8 8

Step	left	right	mid	Adjusted mid	Comparison	Result
1	0	8	4	4	nums[4] == nums[5], 3 != 4	right = 4
2	0	4	2	2	nums[2] == nums[3], 2 != 3	right = 2
3	0	2	1	0	nums[0] == nums[1], 1 == 1	left = 2
4	2	2	-	-	Stop	Return nums[2]

Final answer:

2

Example 2

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

Step	left	right	mid	Adjusted mid	Comparison	Result
1	0	6	3	2	nums[2] == nums[3], 7 == 7	left = 4
2	4	6	5	4	nums[4] == nums[5], 10 != 11	right = 4
3	4	4	-	-	Stop	Return nums[4]

Final answer:

10

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Binary search halves the search space each iteration
Space	O(1)	Only a few variables are used

The algorithm achieves logarithmic time because each iteration discards half of the remaining array. No additional data structures are allocated, so the extra space usage remains constant.

Test Cases

sol = Solution()

assert sol.singleNonDuplicate([1]) == 1  # single element array

assert sol.singleNonDuplicate([1,1,2,3,3]) == 2  # unique element in middle

assert sol.singleNonDuplicate([1,2,2,3,3]) == 1  # unique element at beginning

assert sol.singleNonDuplicate([1,1,2,2,3]) == 3  # unique element at end

assert sol.singleNonDuplicate([3,3,7,7,10,11,11]) == 10  # provided example

assert sol.singleNonDuplicate([1,1,2,2,3,4,4]) == 3  # odd-sized array

assert sol.singleNonDuplicate([0,0,1]) == 1  # smallest valid paired array

assert sol.singleNonDuplicate([5,6,6,7,7]) == 5  # unique at first position

assert sol.singleNonDuplicate([1,1,2,3,3,4,4,5,5]) == 2  # unique near beginning

assert sol.singleNonDuplicate([1,1,2,2,3,3,4]) == 4  # unique at last position

Test	Why
[1]	Verifies single-element boundary case
[1,1,2,3,3]	Tests unique value in middle
[1,2,2,3,3]	Tests unique value at beginning
[1,1,2,2,3]	Tests unique value at end
[3,3,7,7,10,11,11]	Validates provided example
[1,1,2,2,3,4,4]	Tests shifted pairing after unique element
[0,0,1]	Small valid input
[5,6,6,7,7]	Ensures left-edge handling works
[1,1,2,3,3,4,4,5,5]	Tests disruption near beginning
[1,1,2,2,3,3,4]	Ensures correct right-edge handling

Edge Cases

One important edge case occurs when the array contains only one element. In this scenario, the single value is trivially the answer. The implementation handles this naturally because the binary search loop never executes when left == right initially.

Another important edge case occurs when the unique element appears at the beginning of the array. This case can expose incorrect assumptions about pair alignment. For example:

[1,2,2,3,3]

The algorithm correctly detects that the first pairing structure is already broken and narrows the search toward the left side.

A third important edge case occurs when the unique element appears at the end of the array:

[1,1,2,2,3]

Some implementations incorrectly access out-of-range indices when checking neighbors near the end. This solution avoids that issue because mid is always adjusted to an even index and compared safely with mid + 1.

Another subtle edge case involves maintaining correct parity during binary search. If the midpoint is not adjusted to an even index, comparisons may be made against the wrong partner element, producing incorrect results. The explicit parity correction ensures comparisons always align with expected pair boundaries.