540. Single Element in a Sorted Array

Quick Identifier

Topic: binary-search
Pattern: Binary Search (Pair invariant)
Difficulty: Medium
Companies: Google, Amazon, Meta, Apple, Adobe
Frequency: Medium
LeetCode: 540

Quick Sights

Time Complexity: O(log n) from the optimal approach.
Space Complexity: O(1) from the optimal approach.
Core Mechanism: Even-length sorted array where every value appears exactly twice except one value once; return that single element in O(log n) time and O(1) space.

Concept Explanation

Even-length sorted array where every value appears exactly twice except one value once; return that single element in O(log n) time and O(1) space.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

Pairs in sorted order then one singleton
“Logarithmic time” on array with pair structure
After discarding half, remaining side still has even pair structure until singleton isolated

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — O(n) — XOR all values (works but ignores “sorted” hint) or scan pairs.
Better — O(n) — walk pairs by twos.
Optimal — O(log n) time / O(1) space — align mid to even index and compare with neighbor to see which side keeps odd pattern.

Optimal Solution

Go

func singleNonDuplicate(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)/2
		if mid%2 == 1 {
			mid--
		}
		if nums[mid] != nums[mid+1] {
			right = mid
		} else {
			left = mid + 2
		}
	}
	return nums[left]
}

JavaScript

function singleNonDuplicate(nums) {
	let left = 0;
	let right = nums.length - 1;
	while (left < right) {
		let mid = left + Math.floor((right - left) / 2);
		if (mid % 2 === 1) {
			mid--;
		}
		if (nums[mid] !== nums[mid + 1]) {
			right = mid;
		} else {
			left = mid + 2;
		}
	}
	return nums[left];
}