Topics › Binary Search › BS on 1D Arrays

Single element in sorted array

Medium TUF ID 90 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a sorted array of integers in which every value appears exactly twice, except for one value that appears exactly once. Return that single value. The intended solution runs in O(log n) time and O(1) extra space.

Constraints: 1 ≤ n ≤ 10^5, and n is odd (pairs plus one). Values fit in a 32-bit signed integer and may be negative.

Example 1

nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
answer = 2          // every other value has a twin next to it

Example 2

nums = [3, 3, 7, 7, 10, 11, 11]
answer = 10

Approach 1: Brute force, check the neighbours

Intuition. Because the array is sorted, the two copies of a value always sit next to each other. So the single element is the only one that differs from both of its neighbours. At the two ends a neighbour is missing; treat a missing neighbour as “different”.

Algorithm.

1. For each index i, decide whether nums[i] differs from its left neighbour (or i == 0) and from its right neighbour (or i == n - 1).
2. Return the first nums[i] for which both are true.

static int bruteForce(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        boolean leftDiffers = i == 0 || nums[i - 1] != nums[i];
        boolean rightDiffers = i == n - 1 || nums[i + 1] != nums[i];
        if (leftDiffers && rightDiffers) return nums[i];
    }
    throw new IllegalArgumentException("no single element");
}

Complexity. Time O(n): one pass, constant work per index. Space O(1).

Approach 2: Better, XOR everything

Intuition. XOR has three useful properties: a ^ a = 0, a ^ 0 = a, and the order of operations does not matter. XOR-ing the whole array therefore cancels every pair and leaves only the single value. This is shorter and branch-free, but it is still linear, and it never uses the fact that the array is sorted. That is the hint that a faster method exists.

Algorithm.

1. Start with x = 0.
2. XOR every element into x.
3. Return x.

static int better(int[] nums) {
    int x = 0;
    for (int v : nums) x ^= v;
    return x;
}

Complexity. Time O(n), space O(1). It also works on unsorted input, which is why it is the standard answer to the unsorted version of this problem.

Approach 3: Optimal, binary search on pair alignment

Intuition. Look at where the pairs sit. Before the single element, every pair starts at an even index: positions (0, 1), (2, 3), and so on. The single element itself occupies one slot, which shifts everything after it by one. From then on every pair starts at an odd index.

So for an even index i:

• if i is before the single element, nums[i] == nums[i + 1] (a pair starts here);
• if i is the single element or after it, nums[i] != nums[i + 1] (the alignment is broken).

That is a monotonic yes/no question over the even indices: “yes, yes, …, yes, no, no, …”. The first “no” is exactly the index of the single element. Also note that the single element always sits at an even index, because an even number of elements (whole pairs) comes before it.

Algorithm.

1. Set lo = 0, hi = n - 1. Both are even since n is odd.
2. While lo < hi:
   • Take mid and, if it is odd, step it back by one so it is even.
   • If nums[mid] == nums[mid + 1], the pairs are still aligned up to mid + 1, so the single element is to the right: lo = mid + 2.
   • Otherwise the alignment is already broken at mid, so the single element is at mid or to its left: hi = mid.
3. Return nums[lo].

mid + 1 is always a valid index: mid is even, hi is even and mid < hi, so mid ≤ hi - 2. The same argument shows lo = mid + 2 never passes hi, and lo and hi stay even throughout.

static int optimal(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (mid % 2 == 1) mid--;                       // look at the pair that should start at an even index
        if (nums[mid] == nums[mid + 1]) lo = mid + 2;  // pairs still aligned: single is to the right
        else hi = mid;                                 // alignment already broken: single is at mid or left
    }
    return nums[lo];
}

Dry run on Example 1, nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]:

Complexity. Time O(log n): the even-index range halves each step. Space O(1).

A common compact variant compares nums[mid] with nums[mid ^ 1]. For even mid, mid ^ 1 is mid + 1; for odd mid it is mid - 1. In both cases it is the partner mid should have if the pairs are still aligned, so equality means “go right”. It is the same idea with the parity fix folded into a bit trick.

Edge cases and pitfalls

• Single-element array. [1] returns 1. The loop never runs because lo == hi == 0.
• Single element at either end. [0, 1, 1] and [1, 1, 2] are the boundary cases for the neighbour checks in Approach 1 and for the final position of lo in Approach 3. The Java tests also place the single value at every one of 21 possible positions in a 41-element array.
• Forgetting to make mid even. Comparing nums[mid] with nums[mid + 1] at an odd mid asks the wrong question: before the single element, an odd index is the second half of a pair, so the neighbours differ even though everything is aligned.
• Moving lo by only one. lo = mid + 1 makes lo odd and breaks the invariant that the answer is at an even index. Move by two.
• Negative values and zero. Nothing changes: the algorithm only tests equality.
• Overflow. None: there is no arithmetic on values, and lo + (hi - lo) / 2 keeps the midpoint safe.

Related problems

• Single element in a Sorted Array is the same problem in the A2Z sheet.
• Single Number - I is the unsorted version, solved by the XOR trick from Approach 2.
• Find the number that appears once, and other numbers twice. compares hashing, counting and XOR on unsorted input.
• Find peak element is another binary search that decides direction from a local comparison rather than a target value.
• Search element in a sorted and rotated array also binary searches an array that is only “almost” sorted.