540. Single Element in a Sorted Array

Every element in a sorted array appears exactly twice except one. Find that lonely value in O(log n) by exploiting how the pairs line up: before the single element each pair starts on an even index, and that parity flips the moment the single element appears.

● MediumBinary SearchTypeScript

PROBLEM What we're solving

Given a sorted array nums in which every value appears exactly twice except one value that appears once, return that single value. For example nums=[1,1,2,3,3,4,4,8,8] → the answer is 2 (the only un-paired number). Another: nums=[3,3,7,7,10,11,11] → 10. The required complexity is O(log n) time and O(1) space, which rules out a simple linear XOR or scan.

KEY IDEA Pairs start on even indices — until they do not

Insight → walk the array as adjacent pairs at indices (0,1), (2,3), (4,5)…. Beforethe single element, every pair's first copy sits at an even index, so nums[even] === nums[even + 1]. Afterthe single element, the pairing is shifted by one and that equality breaks. So "is the pairing still intact at this even index?" is a monotone yes→no predicate — exactly what binary search needs.

RECIPE Binary search on pair parity

0 · Bounds on the whole array. lo = 0, hi = n - 1. We shrink until lo === hi, which lands on the answer.
1 · Loop while lo < hi. A strict < (not <=) because hi = mid keeps mid in the window — equality would loop forever.
2 · Force mid to be even. mid = lo + ⌊(hi - lo)/2⌋, then if (mid % 2 === 1) mid-- (equivalently mid -= mid & 1). Now mid is the candidate start of a pair, so mid + 1 is always in range.
3 · Compare the pair, eliminate a half. If nums[mid] === nums[mid + 1] the pairing is intact up to here, so the single element is strictly to the right → lo = mid + 2. Otherwise the break is at mid or earlier → hi = mid (keep mid — it might be the answer).
4 · Converge. When the loop ends lo === hi points at the single element. Return nums[lo].

Classic confusion → why lo = mid + 2 but hi = mid (asymmetric)? Because mid is forced even and the pair (mid, mid+1) matched, both cells are ruled out, so jump past them. In the else-branch mid itself can be the lonely element, so it must stay in the window — hence hi = mid, not mid - 1.

COST Complexity & alternatives

Linear scan / XOR

O(n)

XOR-fold every element (pairs cancel) or scan pairs. Correct, but reads all n values.

Binary search on parity

O(log n)

O(log n) time, O(1) space — touches only ~log₂ n elements.

Why the linear answer is not enough

nums.reduce((a, b) => a ^ b, 0) returns the single value in O(n) because each duplicate XORs to zero. It is beautiful but reads the whole array — the problem explicitly demands O(log n), so you must use the sorted/pairing structure.

Pattern transfer → this is binary search on a monotone predicate rather than on a value, the same lens behind First Bad Version, Find Minimum in Rotated Sorted Array(where the "sortedness" flips once), and Search Insert Position. Whenever an array has a single yes→no boundary, binary search finds it in O(log n).

RUN IT Force mid even, follow the broken pairing

nums =

step 0 / 7

STARTSearch begins. lo=0, hi=8. Amber cells are the live window; we converge until lo === hi.

1function singleNonDuplicate(nums: number[]): number {
2▶  let lo = 0;
3▶  let hi = nums.length - 1;
4 
5  while (lo < hi) {
6    let mid = lo + Math.floor((hi - lo) / 2);
7    if (mid % 2 === 1) mid--;            // force mid to be even
8 
9    if (nums[mid] === nums[mid + 1]) {   // pairing intact → single is right
10      lo = mid + 2;
11    } else {                             // pairing broken → single is here or left
12      hi = mid;
13    }
14  }
15  return nums[lo];   // lo === hi → the lonely element
16}

nums =101122333445468788

State

—

mid

—

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

active windowmid pair (probe)the single element

slowfast

TYPESCRIPT The solution, annotated

singleNonDuplicate.ts
function singleNonDuplicate(nums: number[]): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (mid % 2 === 1) mid--;            // force mid to be even

    if (nums[mid] === nums[mid + 1]) {   // pairing intact → single is right
      lo = mid + 2;
    } else {                             // pairing broken → single is here or left
      hi = mid;
    }
  }
  return nums[lo];   // lo === hi → the lonely element
}

Reading it block by block

Lines 2–3 — bounds over the whole array. lo = 0 and hi = nums.length - 1. Unlike classic target search we are not looking for a value but converging two pointers onto a single surviving index.

Line 5 — loop while lo < hi. Strict less-than. Because the else-branch sets hi = mid (keeping mid), a <= condition could leave lo === hi === mid and spin forever. The window shrinks until exactly one index remains.

Lines 6–7 — force mid to be even. Compute the midpoint, then if it is odd subtract one. Now mid is the start of a pair, so its partner mid + 1 is guaranteed in range and we can compare a clean pair.

Lines 9–13 — compare the pair and discard a half. If nums[mid] === nums[mid + 1] the pairing has held up to here, so the lonely element is strictly to the right → lo = mid + 2. Otherwise the parity already broke at or before mid → hi = mid (we must keep mid because it could itself be the answer).

Line 16 — return the survivor. The loop exits when lo === hi; that index is the single element, so return nums[lo].

Complexity → O(log n) time — each iteration discards half the remaining pairs. O(1) extra space — two integer pointers and a midpoint, no auxiliary structure.

INTERVIEWFollow-ups they'll ask

"Can you do it without forcing mid even?" Yes — compare nums[mid] with its partner chosen by parity: mid ^ 1 gives the sibling index (even→+1, odd→−1). If they are equal the single is to the right, else left. Same O(log n), no explicit adjustment.
"What is the O(n) baseline?" XOR every element: nums.reduce((a, b) => a ^ b, 0). Pairs cancel, leaving the single value. Simple and clever, but O(n) — fails the stated O(log n) requirement.
"Why must the array be sorted?" The pairing/parity invariant depends on duplicates being adjacent. On an unsorted array the predicate is not monotone, so binary search cannot apply — you fall back to the XOR/hash O(n) approach.
"What if more than one element were single?" The yes→no boundary is no longer well-defined (multiple parity breaks), so this exact binary search breaks. You would need a different technique entirely.
"How do you know the answer index is even?" Everything before the single element pairs up perfectly, so it occupies an even count of cells — the single element therefore sits at an even index, and lo always lands there.

OPTIMAL Binary Search

singleNonDuplicate.ts
function singleNonDuplicate(nums: number[]): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (mid % 2 === 1) mid--;            // force mid to be even

    if (nums[mid] === nums[mid + 1]) {   // pairing intact → single is right
      lo = mid + 2;
    } else {                             // pairing broken → single is here or left
      hi = mid;
    }
  }
  return nums[lo];   // lo === hi → the lonely element
}

Complexity → O(log n) time — each iteration discards half the remaining pairs. O(1) extra space — two integer pointers and a midpoint, no auxiliary structure.

ALT 1 XOR fold — cancel the pairs

O(n) time · O(1) space

Ignore the sorted structure and XOR every element together. Each duplicated value cancels to zero, leaving only the single element — elegant and one line, but O(n).

approach-2.ts
function singleNonDuplicate(nums: number[]): number {
  return nums.reduce((acc, x) => acc ^ x, 0);
}

Note → This is correct on any array (sorted or not) and uses O(1) space, but it reads all n values. The problem demands O(log n), so it is only acceptable when the constraint is relaxed.

ALT 2 Parity-sibling binary search — no explicit mid adjustment

O(log n) time · O(1) space

Instead of forcing mid even, compare it to its parity sibling mid ^ 1 (even→+1, odd→−1).

approach-3.ts
function singleNonDuplicate(nums: number[]): number {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === nums[mid ^ 1]) lo = mid + 1; // pair intact → go right
    else                              hi = mid;     // break here or left
  }
  return nums[lo];
}

Note → mid ^ 1 flips the lowest bit, mapping each index to its partner in the pair. Functionally identical to forcing mid even — pick whichever you find clearer.

MNEMONIC The one-liner

"Pairs hug even indices; snap mid even, follow the broken pair."

TRIGGERS When you see _ → reach for _

sorted, all paired except one, need O(log n)	binary search on pair parity
monotone yes→no boundary in an array	binary search the predicate, hi = mid
no O(log n) constraint, just find the unpaired	XOR-fold all elements (O(n))
need the sibling of an index by parity	use mid ^ 1 (even↔odd partner)

SKELETON The reusable shape

skeleton.ts
function singleNonDuplicate(nums: number[]): number {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    mid -= mid & 1;                  // make mid even
    if (nums[mid] === nums[mid + 1]) lo = mid + 2;
    else                              hi = mid;
  }
  return nums[lo];
}

FLASHCARDS Tap to flip

What is the core invariant the binary search exploits?

Before the single element, each pair's first copy is at an even index, so nums[even] === nums[even + 1]. After it, that equality breaks — a monotone yes→no boundary.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For nums = [1,1,2,3,3,4,4,8,8], what value does the algorithm return?

QUESTION 02

What time complexity does this problem require, ruling out a plain scan?

QUESTION 03

Why is mid forced to an even index with if (mid % 2 === 1) mid--?

QUESTION 04

When nums[mid] === nums[mid + 1] (mid even), what do you do?

QUESTION 05

In the else-branch the code sets hi = mid rather than hi = mid - 1. Why?

QUESTION 06

Why is the loop condition lo < hi instead of lo <= hi?

QUESTION 07

Which alternative correctly finds the single element but fails the complexity requirement?

QUESTION 08

#540 · Single Element in a Sorted ArrayEvery element appears twice except one; find it in O(log n) by binary searching on pair parity — before the loner the first of each pair sits on an even index, after it the alignment shifts.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Pairs start on even indices — until they do not

RECIPE Binary search on pair parity

COST Complexity & alternatives

Why the linear answer is not enough

RUN IT Force mid even, follow the broken pairing

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Binary Search

ALT 1 XOR fold — cancel the pairs

ALT 2 Parity-sibling binary search — no explicit mid adjustment

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _