Workspace

Problem workspace

3 day streakD

Single Element in a Sorted Array

MediumBinary SearchRotations & structure

The challenge

Return the single value that appears once when every other value appears exactly twice.

Sorted, nonempty array of odd length; exactly one singleton and all other counts are two.

Example

[1, 1, 2, 3, 3, 4, 4] → 2.

Use the walkthrough below to inspect the input and each state change.

See Pair parity, step by step

Inspect the comparison, the invariant, and the next boundary.

Inclusive candidate indices
L = 0 · mid = — · R = 610112233344546
Current comparisonResolved positionNumbers below = indices
Left
0
Middle
—
Right
6
Step 01 / 4

Start with the candidate indices

The retained interval contains the answer whenever it exists. Watch why each comparison can discard one side.

left = 0; right = 6

Recorded result so far

Not resolved
View exact input

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

Put it into code

Before the singleton, pairs start at even indices. Align mid to an even index so a pair comparison tells you which side changed parity.

Indices are zero-based. C++ uses C++17 or later.

def single_element(nums):
    # Sorted, nonempty; one singleton, all others occur exactly twice.
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        mid -= mid % 2  # First index of a candidate pair.
        if nums[mid] == nums[mid + 1]:
            left = mid + 2
        else:
            right = mid
    return nums[left]

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap