Single Element in a Sorted Array

Description

Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

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

Example 2:
Input: nums = [3,3,7,7,10,11,11]
Output: 10

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

---

Brute Force Approach: Bitwise XOR

Intuition

XOR all elements together. Since $a\oplus a=0$ and $a\oplus 0=a$, all duplicate pairs cancel each other out, leaving only the single unique element.

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

Complexity

• Time Complexity: $O(N)$ — Scans through all $N$ elements once.
• Space Complexity: $O(1)$ — Uses constant extra memory.

---

Binary Search Approach 1: Subarray Size Check

Intuition

At index m, check if nums[m] matches its left or right neighbor to identify its pair. Calculate the size of the left portion (leftSize). If leftSize is odd, the single element lies in the left half; otherwise, it lies in the right half.

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
 
        while (l <= r) {
            int m = l + (r - l) / 2;
 
            // Check if m is the single element
            if ((m - 1 < 0 || nums[m - 1] != nums[m]) && 
                (m + 1 == nums.length || nums[m] != nums[m + 1])) {
                return nums[m];
            }
 
            // Determine boundary index of the left pair
            int leftSize = (m - 1 >= 0 && nums[m - 1] == nums[m]) ? m - 1 : m;
 
            // If left subarray size is odd, target is on the left side
            if (leftSize % 2 == 1) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
 
        return -1;
    }
}
 

Complexity

• Time Complexity: $O(\log N)$ — Standard binary search halving the search space.
• Space Complexity: $O(1)$ — Constant auxiliary space.

---

Binary Search Approach 2: Binary Search on Even Indices

Intuition

Before the single element, every pair starts on an even index (nums[even] == nums[even + 1]). Force m to be an even index. If nums[m] == nums[m + 1], the disruption hasn’t happened yet, so search right (l = m + 2). Otherwise, search left (r = m).

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
 
        while (l < r) {
            int m = l + (r - l) / 2;
 
            // Ensure m is always even
            if (m % 2 != 0) {
                m--;
            }
 
            // If pair matches, single element is strictly to the right
            if (nums[m] == nums[m + 1]) {
                l = m + 2;
            } else {
                r = m;
            }
        }
 
        return nums[l];
    }
}
 

Complexity

• Time Complexity: $O(\log N)$ — Binary search operating over even index candidates.
• Space Complexity: $O(1)$ — Constant auxiliary space.

---

Most Optimized Solution: Binary Search with Bitwise XOR Partner Index (m ^ 1)

Intuition

Use bitwise XOR (m ^ 1) to dynamically find the expected partner index of m regardless of whether m is even or odd:

• If m is even, m ^ 1 equals m + 1.
• If m is odd, m ^ 1 equals m - 1.

If nums[m] == nums[m ^ 1], the pair is intact and in proper order, meaning we are still to the left of the single element, so move right (l = m + 1). Otherwise, the single element is at or before m (r = m).

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
 
        while (l < r) {
            int m = l + (r - l) / 2;
 
            if (nums[m] == nums[m ^ 1]) {
                l = m + 1; // Left side intact -> search right
            } else {
                r = m;     // Single element is at or to the left of m
            }
        }
 
        return nums[l];
    }
}
 

Complexity

• Time Complexity: $O(\log N)$ — Halves the search space each step.
• Space Complexity: $O(1)$ — Uses no extra space.

---

Easy Memory Rule

“For $O(\log N)$ single element: m ^ 1 finds partner index. If nums[m] == nums[m ^ 1] $\to$ l = m + 1, else $\to$ r = m.”

When you reach the else statement (nums[m] != nums[m + 1]), nums[m] could be the single element, but it could also be the second half of a pair located somewhere to the right of the single element.

---

Concrete Example

Consider this array where 3 at index 4 is the single element:

$\begin{array}{cccccccccc}\text{Index:}& 0& 1& 2& 3& 4& 5& 6& 7& 8\\ \text{Value:}& 1& 1& 2& 2& 3& 4& 4& 5& 5\end{array}$

Suppose binary search chooses m = 6 (which is an even index):

• nums[6] is 4
• nums[6 + 1] (index 7) is 5
• Check: nums[6] == nums[7] $\to$ 4 == 5 is False!

We enter the else block:

• Is nums[6] (value 4) our single element? No!
• Value 4 is actually part of the pair [4, 4] at indices (5, 6).
• Because the single element 3 appears at index 4, it shifted all subsequent pairs so they now start on odd indices instead of even indices (4 is at indices 5, 6 instead of 6, 7).

---

Why we do r = m

Entering the else branch only proves one thing:

“The disruption (single element) has already happened at or before index m.”

1. It could be at index m (e.g., if m = 4, nums[4] = 3 != nums[5] = 4).
2. It could be somewhere to the left of m (e.g., if m = 6, the single element 3 is at index 4).

Because nums[m] might actually be the answer, we cannot eliminate m completely (so we don’t do r = m - 1). Instead, we set r = m to keep index m inside our search window and continue searching the left half.