☕ DSA Java Articles

Topics › Binary Search › BS on 1D Arrays

Single element in a Sorted Array

Medium TUF ID 2770 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a sorted array arr of n integers in which every value appears exactly twice, except for one value that appears exactly once. Return that single value. Because the array is sorted, the two copies of every duplicated value sit next to each other, and n is always odd.

Constraints: 1 ≤ n ≤ 10^5, n is odd, values fit in a 32-bit signed integer. Exactly one value appears once; every other value appears exactly twice.

Example 1

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

Example 2

arr = [3, 3, 7, 7, 10, 11, 11]
answer = 10         // 10 sits between the pair (7, 7) and the pair (11, 11)

Approach 1: Brute force, compare with the neighbours

Intuition. Because duplicates are adjacent, the single element is the only one whose value differs from both its left neighbour and its right neighbour. The first and last positions have only one neighbour, so they need their own comparison. A single left-to-right scan finds it.

Algorithm.

  1. If n == 1, the only element is the answer.
  2. For every index i:
    • If i == 0, return arr[0] when arr[0] != arr[1].
    • If i == n - 1, return arr[n-1] when arr[n-1] != arr[n-2].
    • Otherwise return arr[i] when it differs from both arr[i-1] and arr[i+1].
  3. The loop always finds the answer for valid input; -1 is returned only for malformed arrays.
static int bruteForce(int[] arr) {
    int n = arr.length;
    if (n == 1) return arr[0];
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            if (arr[0] != arr[1]) return arr[0];
        } else if (i == n - 1) {
            if (arr[n - 1] != arr[n - 2]) return arr[n - 1];
        } else if (arr[i] != arr[i - 1] && arr[i] != arr[i + 1]) {
            return arr[i];
        }
    }
    return -1;
}

Complexity. Time O(n): each index is examined once with a constant number of comparisons. Space O(1): no extra storage.

This is already linear, but the problem explicitly asks for O(log n), which is the real exercise here. It is also worth noticing that this approach does not depend on sortedness beyond “duplicates are adjacent”.

Approach 2: Better, XOR everything

Intuition. XOR has two properties that make it perfect for “everything appears twice except one”: a ^ a = 0 and a ^ 0 = a, and the operation is commutative and associative, so the order of the elements does not matter. XOR-ing the whole array makes every pair cancel to 0, leaving exactly the single value.

Algorithm.

  1. Start with x = 0.
  2. XOR every element into x.
  3. Return x.
static int better(int[] arr) {
    int x = 0;
    for (int v : arr) x ^= v;
    return x;
}

Complexity. Time O(n): one pass. Space O(1).

This is the neatest linear solution and it even works for unsorted arrays. It is not faster than Approach 1 asymptotically, but it is branch-free and worth knowing because the same trick solves several “find the odd one out” problems. It still does not use the sorted order, so it cannot reach O(log n).

Approach 3: Optimal, binary search on index parity

Intuition. Look at the indices of each pair. Before the single element, pairs occupy positions (0,1), (2,3), (4,5), ...: the first copy is at an even index and the second at an odd index. After the single element, everything is shifted by one: pairs occupy (odd, even) positions instead. So at any index mid we can tell which side of the single element we are on by checking whether arr[mid] pairs with the “expected” neighbour:

If arr[mid] matches neither neighbour, it is the single element.

To avoid index checks inside the loop, handle the two ends up front: if arr[0] != arr[1] the answer is arr[0], and if arr[n-1] != arr[n-2] the answer is arr[n-1]. After that the search range [1, n-2] always has a valid neighbour on both sides.

Algorithm.

  1. If n == 1, return arr[0]. If arr[0] != arr[1], return arr[0]. If arr[n-1] != arr[n-2], return arr[n-1].
  2. Set lo = 1, hi = n - 2.
  3. While lo <= hi:
    • mid = lo + (hi - lo) / 2.
    • If arr[mid] differs from both neighbours, return it.
    • Determine inLeftHalf: for odd mid it is arr[mid] == arr[mid-1], for even mid it is arr[mid] == arr[mid+1].
    • If inLeftHalf, set lo = mid + 1; otherwise set hi = mid - 1.
static int optimal(int[] arr) {
    int n = arr.length;
    if (n == 1) return arr[0];
    if (arr[0] != arr[1]) return arr[0];
    if (arr[n - 1] != arr[n - 2]) return arr[n - 1];
    int lo = 1, hi = n - 2;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] != arr[mid - 1] && arr[mid] != arr[mid + 1]) return arr[mid];
        // Left of the single element every pair starts at an even index: (0,1), (2,3), ...
        boolean inLeftHalf = (mid % 2 == 1) ? arr[mid] == arr[mid - 1] : arr[mid] == arr[mid + 1];
        if (inLeftHalf) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Dry run on arr = [1, 1, 2, 3, 3, 4, 4, 8, 8] (n = 9). The ends are both proper pairs, so we search [1, 7].

lo hi mid arr[mid-1], arr[mid], arr[mid+1] mid parity inLeftHalf? action
1 7 4 3, 3, 4 even arr[4] == arr[5]? no hi = 3
1 3 2 1, 2, 3 even differs from both return 2

Why does the half we discard never contain the answer? If inLeftHalf is true, the pair containing mid starts at an even index, which is only possible when no single element precedes it, so indices ≤ mid + 1 are all proper pairs and the answer is strictly to the right. If it is false, the pair containing mid starts at an odd index, which can only happen after the single element, so the answer is strictly to the left. Each step therefore halves the range while keeping the answer inside it.

Complexity. Time O(log n): the range is halved on every iteration. Space O(1).

Edge cases and pitfalls