Single Element in a Sorted Array

Master this topic with zero to advance depth.

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. Find this single element that appears only once. Your solution must run in $O(\\log N)$ time and $O(1)$ space.

Medium

Examples

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

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

Approach 1

Level I: XOR Manipulation

Intuition

XORing a number with itself results in 0. XORing 0 with any number results in that number. If we XOR all elements, the pairs will cancel out, leaving the single element.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

nums = [1,1,2] 1 ^ 1 ^ 2 = 0 ^ 2 = 2. Result: 2.

java

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

Approach 2

Level II: Linear Scan (Pairs)

Intuition

Since the array is sorted, we can check elements in pairs. If nums[i] is not equal to nums[i+1], then nums[i] is the single element.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

nums = [1,1,2,3,3]

i=0: nums[0]==nums[1] (1==1). Continue.
i=2: nums[2]!=nums[3] (2!=3). Return nums[2]=2.

java

class Solution {
    public int singleNonDuplicate(int[] nums) {
        for (int i = 0; i < nums.length - 1; i += 2) {
            if (nums[i] != nums[i + 1]) return nums[i];
        }
        return nums[nums.length - 1];
    }
}

Approach 3

Level III: Optimal (Binary Search on Even Indices)

Intuition

In a paired array, pairs start at even indices: (0,1), (2,3), etc. Before the single element, nums[even] == nums[even+1]. After the single element, this pattern breaks. We search for the first index where nums[even] != nums[even+1].

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	Mid_Even	nums[M_E] == nums[M_E+1]	Decision
1	0	8	4	4	3 == 4 (No)	R = 4
2	0	4	2	2	2 == 3 (No)	R = 2
Exit	2	2	-	-	-	Return nums[2] = 2

java

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

← Previous QuestionSearch a 2D Matrix

Next Question →Find K Closest Elements

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.