Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The array is sorted, and every value appears exactly twice except for one value that appears once.

If the array were not sorted, the quickest idea would be XOR: identical values cancel out, so the final XOR is the answer. That works in O(n) time and O(1) space.

But the sorted order is the real gift here. The interviewer is usually testing whether that extra structure can be turned into something faster than a full scan. The target answer is O(log n) time with O(1) extra space, which points directly to binary search.

The pattern hidden in the sorted pairs

The key observation is that the single value shifts the pairing pattern.

Before the single value, each pair starts at an even index:

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

Index positions:

0 1 2 3 4 5 6 7 8

Here the singleton is 4 at index 6.

Look at the pairs before it:

  • 1 is at (0, 1)
  • 2 is at (2, 3)
  • 3 is at (4, 5)

Those all start at even indices.

After the single value appears, everything to its right is shifted by one, so the remaining pairs start at odd indices:

  • 5 is at (7, 8)

That even/odd flip is exactly what binary search can test.

Two solution paths

The baseline solution is XOR. It is short, reliable, and uses constant extra space, but it still has to read every element, so it is O(n).

The optimal solution uses binary search on pair boundaries. Pick a middle position, force it to the start of a potential pair, and compare that element with its neighbor.

If the pair is valid, the singleton must be to the right, because everything up to that pair still has the normal even-index alignment. If the pair is broken, the singleton is at that position or somewhere to the left.

That gives O(log n) time and O(1) extra space.

How to derive the binary search in an interview

  1. Start from the linear XOR idea to show you understand the core constraint.
  2. Notice the problem statement says the array is sorted, which XOR ignores.
  3. Ask what sortedness changes. It makes duplicates adjacent.
  4. Notice that before the singleton, pairs begin at even indices, and after it, they begin at odd indices.
  5. Build a binary search that checks whether the middle pair still follows the normal even-index alignment.

That is the clean derivation: the algorithm is not “binary search because the array is sorted.” It is binary search because the singleton creates a monotonic change in pair alignment.

Python solution

from typing import List, Sequence


class SingleElementFinder:
    """Find the lone value in a sorted array of adjacent pairs."""

    def find_unique_value(self, values: Sequence[int]) -> int:
        self._validate_input(values)

        left_index = 0
        right_index = len(values) - 1

        while left_index < right_index:
            # Force the probe onto the first index of a potential pair so the
            # comparison always checks (even_index, even_index + 1).
            pair_start_index = self._pair_start_index(left_index, right_index)

            if values[pair_start_index] == values[pair_start_index + 1]:
                left_index = pair_start_index + 2
            else:
                right_index = pair_start_index

        return values[left_index]

    def _pair_start_index(self, left_index: int, right_index: int) -> int:
        middle_index = (left_index + right_index) // 2
        if middle_index % 2 == 1:
            middle_index -= 1
        return middle_index

    def _validate_input(self, values: Sequence[int]) -> None:
        if not values:
            raise ValueError("values must not be empty")
        if len(values) % 2 == 0:
            raise ValueError("values must contain an odd number of elements")


class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        finder = SingleElementFinder()
        return finder.find_unique_value(nums)

Why this works

The algorithm keeps one invariant: the singleton is always inside the current search interval.

At each step, it probes an even index and compares that element with the next one. If they match, that whole pair is complete and the singleton must be to the right. If they do not match, the normal pairing pattern has already broken, so the singleton must be at that index or somewhere to the left.

Because each iteration removes roughly half of the remaining interval, the time complexity is O(log n). Only a few index variables are stored, so the extra space is O(1).

Interview follow-ups

What if the array were not sorted?

Then the binary-search structure disappears, because equal values are no longer guaranteed to sit next to each other. The clean answer is XOR. Iterate once through the array, XOR every value into an accumulator, and return the final result. Every duplicated value cancels itself out because x ^ x = 0, leaving only the unique value behind. That approach works in O(n) time and O(1) space. The tradeoff is that it gives up the O(log n) runtime that was only possible because of the sorted input.

Why does forcing the middle index to be even make the logic work?

The binary search is reasoning about pair starts, not arbitrary positions. In the normal part of the array, valid pairs begin at even indices and occupy (even, even + 1). If the probe lands on an odd index, comparing it directly can mix the end of one pair with the start of another and make the test harder to reason about. By shifting an odd middle index left by one, the algorithm always checks a clean candidate pair boundary. That makes the comparison deterministic: a match means the singleton is still to the right, and a mismatch means the break has already happened. The complexity stays O(log n) time and O(1) space.

What if the interviewer wants the index of the single element instead of the value?

Almost nothing changes. The same binary search already converges on the unique element’s index. Instead of returning values[left_index], the helper can return left_index. The reason this works is that the search interval shrinks around the first location where the pair pattern stops being valid, and that location is exactly the singleton’s position. The runtime and space bounds stay the same: O(log n) time and O(1) extra space.

What if every other number appeared three times instead of twice?

That becomes a different problem. The neat even/odd pairing trick no longer applies, because the sorted structure is based on groups of size three rather than adjacent pairs, so the simple binary-search invariant breaks. A practical general-purpose answer is bit counting: count how many times each bit is set across all numbers, take each count modulo 3, and rebuild the unique value from the remaining bits. That works in O(n) time and O(1) extra space if the integer width is fixed. The tradeoff is that it is no longer using the sorted order; it is solving a more general repeated-count variant.

Practical takeaway

This problem looks like a duplicate-removal question, but it is really a pattern-change question.

Once the array is viewed as “pairs before the singleton, shifted pairs after it,” the binary search becomes straightforward. That is the interview move that separates the O(n) answer from the optimal O(log n) one.