Single Element in a Sorted Array

Q: What is the best time complexity for Single Element in a Sorted Array?

Optimal (binary search on pair alignment) runs in O(log n) time and O(1) extra space.

Q: Which pattern does Single Element in a Sorted Array use?

It is a binary search problem that uses the unique 1-d binary search pattern. Other problems with the same pattern: First Bad Version, Find Peak Element.

Q: Is there a brute force solution for Single Element in a Sorted Array?

Yes. XOR everything takes O(n) time and O(1) space. Pairs cancel under XOR, leaving the single value.

Q: Which edge cases should I test for Single Element in a Sorted Array?

The single value is first or last; Length 1.

Medium Binary Search Unique 1-D Binary Search Original on LeetCode

Single Element in a Sorted Array is a medium binary search problem solved with the unique 1-d binary search pattern. The best approach, optimal (binary search on pair alignment), runs in O(log n) time and O(1) space. Below are 2 approaches in Java, from xor everything up.

Problem

In a sorted array, every value appears exactly twice except one value that appears once. Find it in O(log n) time and O(1) space.

Examples

Example 1

Input: nums = [1, 1, 2, 3, 3, 4, 4]
Output: 2

Example 2

Input: nums = [5, 7, 7, 9, 9]
Output: 5

Constraints

1 <= nums.length <= 10^5 (always odd)
Every value appears twice except one. O(log n) time, O(1) space.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
XOR everything	`O(n)`	`O(1)`
Optimal (binary search on pair alignment)	`O(log n)`	`O(1)`

1XOR everything

TimeO(n)

SpaceO(1)

Pairs cancel under XOR, leaving the single value.

x ^= each value; return x.

Java

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int x = 0;
        for (int v : nums) x ^= v;
        return x;
    }
}

2Optimal (binary search on pair alignment)

TimeO(log n)

SpaceO(1)

Look only at even indices mid. If nums[mid] == nums[mid + 1], the pairs are still aligned up to here, so the single element is to the right. Otherwise it is at mid or to the left.

lo = 0, hi = n - 1.
mid = lo + (hi - lo) / 2; if mid is odd, mid--.
If nums[mid] == nums[mid + 1], lo = mid + 2; else hi = mid.
Return nums[lo].

Java

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (mid % 2 == 1) mid--;
            if (nums[mid] == nums[mid + 1]) lo = mid + 2;
            else hi = mid;
        }
        return nums[lo];
    }
}

Edge cases to test

The single value is first or last
Length 1

Hints

Hint 1

Before the single element, pairs start at even indices. After it, they start at odd indices.

FAQ

What is the best time complexity for Single Element in a Sorted Array?

Optimal (binary search on pair alignment) runs in O(log n) time and O(1) extra space.

Which pattern does Single Element in a Sorted Array use?

It is a binary search problem that uses the unique 1-d binary search pattern. Other problems with the same pattern: First Bad Version, Find Peak Element.

Is there a brute force solution for Single Element in a Sorted Array?

Yes. XOR everything takes O(n) time and O(1) space. Pairs cancel under XOR, leaving the single value.

Which edge cases should I test for Single Element in a Sorted Array?

The single value is first or last; Length 1.