Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Single Element in a Sorted Array

MEDIUMProblemSolveExternal Links

Description

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.

Examples

Example 1

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

Output: 2

Explanation: Every element except 2 appears exactly twice: 1 appears at indices 0 and 1, 3 at indices 3 and 4, 4 at indices 5 and 6, and 8 at indices 7 and 8. The value 2 at index 2 is the only element that appears once.

Example 2

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

Output: 10

Explanation: The pairs are (3,3), (7,7), and (11,11). The value 10 at index 4 has no pair — it is the single element.

Example 3

Input: nums = [1]

Output: 1

Explanation: There is only one element in the array, so it is trivially the single element.

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • 0 ≤ nums[i] ≤ 10^5
  • nums is sorted in non-decreasing order
  • Every element appears exactly twice except for one element which appears exactly once
  • nums.length is always odd (pairs + one single = odd)

Editorial

Brute Force

Intuition

The simplest idea: since every element appears twice except one, we can use the XOR trick. XORing a number with itself gives 0, and XORing with 0 leaves the number unchanged. If we XOR all elements together, every paired element cancels out, leaving only the single element.

Alternatively, we can scan the sorted array two elements at a time: check if nums[i] == nums[i+1]. If they match, skip the pair. The first index where they don't match tells us where the single element is.

The XOR approach is elegant, but it scans every element — O(n) time. The pairwise scan also takes O(n). Both work correctly but don't meet the O(log n) requirement.

Step-by-Step Explanation

Let's trace the pairwise scan approach with nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]:

Step 1: Start at i = 0. Check pair: nums[0] = 1, nums[1] = 1. They match → this is a pair. Skip to i = 2.

Step 2: i = 2. Check pair: nums[2] = 2, nums[3] = 3. They DON'T match → nums[2] = 2 is the single element!

Result: Return 2.

Now let's trace with nums = [3, 3, 7, 7, 10, 11, 11]:

Step 1: i = 0. nums[0] = 3, nums[1] = 3. Match → skip to i = 2.

Step 2: i = 2. nums[2] = 7, nums[3] = 7. Match → skip to i = 4.

Step 3: i = 4. nums[4] = 10, nums[5] = 11. DON'T match → nums[4] = 10 is the single element.

Result: Return 10.

Brute Force — Pairwise Scan — Watch how we scan pairs of adjacent elements. When a pair doesn't match, the first element of that mismatch is the single element.

XOR approach trace: XOR all elements: 1⊕1⊕2⊕3⊕3⊕4⊕4⊕8⊕8 = (1⊕1)⊕2⊕(3⊕3)⊕(4⊕4)⊕(8⊕8) = 0⊕2⊕0⊕0⊕0 = 2. Same answer, but requires visiting every element.

Algorithm

Pairwise Scan:

  1. Iterate i from 0 to n-1 with step size 2
  2. If i is the last index (i == n-1), return nums[i] (it's the single element at the end)
  3. If nums[i] ≠ nums[i+1], return nums[i]
  4. If we exit the loop, no single element was found (shouldn't happen per constraints)

XOR Alternative:

  1. Initialize result = 0
  2. XOR every element: result ^= nums[i]
  3. Return result

Code

#include <vector>
using namespace std;

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i += 2) {
            if (i == nums.size() - 1) return nums[i];
            if (nums[i] != nums[i + 1]) return nums[i];
        }
        return -1; // unreachable
    }
};
class Solution:
    def singleNonDuplicate(self, nums: list[int]) -> int:
        for i in range(0, len(nums), 2):
            if i == len(nums) - 1:
                return nums[i]
            if nums[i] != nums[i + 1]:
                return nums[i]
        return -1  # unreachable
class Solution {
    public int singleNonDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i += 2) {
            if (i == nums.length - 1) return nums[i];
            if (nums[i] != nums[i + 1]) return nums[i];
        }
        return -1; // unreachable
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case (single element at the very end), we scan through all n/2 pairs, visiting up to n elements. This is linear time.

Space Complexity: O(1)

We use only a loop variable. No additional data structures.

Why This Approach Is Not Efficient

The brute force runs in O(n) time, but the problem explicitly requires O(log n) time. For n up to 10^5, linear is fast enough in practice, but it doesn't satisfy the constraint and wastes the sorted property of the array.

The crucial observation that unlocks O(log n) is about pair alignment:

Before the single element: Every pair occupies an (even, odd) index pair. For example, in [1, 1, 2, 3, 3, ...], the pair (1,1) sits at indices (0, 1) — the first copy is at an even index, the second at an odd index.

After the single element: The alignment shifts. Every pair now occupies an (odd, even) index pair. For example, in [..., 2, 3, 3, 4, 4, 8, 8], after the single element 2, the pair (3,3) sits at indices (3, 4) — the first copy is at an odd index.

This alignment shift is the key: we can use binary search to check whether the single element is to the left or right of the mid position by checking the pair alignment at mid. If the pair alignment at mid is still (even, odd), the single element is to the right. If it's broken, the single element is at or to the left of mid.

Optimal Approach - Binary Search on Pair Alignment

Intuition

The key insight is that the single element disrupts the pairing pattern in the sorted array.

In a sorted array where every element appears twice, pairs naturally align at (even_index, odd_index):

  • Index 0,1 → first pair
  • Index 2,3 → second pair
  • Index 4,5 → third pair
  • ...

When the single element is inserted, it shifts all subsequent pairs by one position. So:

  • Left of the single element: pairs are at (even, odd) positions
  • Right of the single element: pairs are at (odd, even) positions

This creates a binary property we can search on:

  • If mid is even and nums[mid] == nums[mid + 1], the pair at mid is properly aligned → the single element is to the right
  • If mid is even and nums[mid] != nums[mid + 1], the alignment is broken → the single element is at mid or to the left
  • Similar logic applies when mid is odd (we check nums[mid] == nums[mid - 1])

To simplify, we can always work with even indices. If mid is odd, we decrement it to the previous even index, ensuring we always check the start of a potential pair.

Step-by-Step Explanation

Let's trace with nums = [1, 1, 2, 3, 3, 4, 4, 8, 8], target single = 2:

Step 1: left = 0, right = 8. mid = (0+8)/2 = 4. Make mid even: 4 is even ✓.
Check: nums[4] = 3, nums[5] = 4. Are they equal? NO → pair alignment is broken at mid. The single element is at index 4 or to the left. Set right = 4.

Step 2: left = 0, right = 4. mid = (0+4)/2 = 2. mid is even ✓.
Check: nums[2] = 2, nums[3] = 3. Are they equal? NO → pair alignment broken. Single element is at index 2 or to the left. Set right = 2.

Step 3: left = 0, right = 2. mid = (0+2)/2 = 1. mid is odd → adjust to 0.
Check: nums[0] = 1, nums[1] = 1. Are they equal? YES → pair properly aligned. Single element is to the RIGHT. Set left = 0 + 2 = 2.

Step 4: left = 2, right = 2. left == right → found! Return nums[2] = 2.

Binary Search on Pair Alignment — Watch how binary search checks whether the pair alignment at mid is intact or broken to determine which half contains the single element.

Algorithm

  1. Initialize left = 0, right = n - 1
  2. While left < right:
    • Compute mid = left + (right - left) / 2
    • If mid is odd, decrement mid by 1 (ensure mid is even — we always check the start of a potential pair)
    • If nums[mid] == nums[mid + 1]: the pair at mid is properly aligned → single element is to the right. Set left = mid + 2
    • Else: pair alignment is broken → single element is at mid or to the left. Set right = mid
  3. Return nums[left] (left == right at this point)

Code

#include <vector>
using namespace std;

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // Ensure mid is even
            if (mid % 2 == 1) mid--;
            
            if (nums[mid] == nums[mid + 1]) {
                // Pair is aligned → single element is to the right
                left = mid + 2;
            } else {
                // Pair is broken → single element is at mid or left
                right = mid;
            }
        }
        
        return nums[left];
    }
};
class Solution:
    def singleNonDuplicate(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while left < right:
            mid = left + (right - left) // 2
            
            # Ensure mid is even
            if mid % 2 == 1:
                mid -= 1
            
            if nums[mid] == nums[mid + 1]:
                # Pair is aligned → single element is to the right
                left = mid + 2
            else:
                # Pair is broken → single element is at mid or left
                right = mid
        
        return nums[left]
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // Ensure mid is even
            if (mid % 2 == 1) mid--;
            
            if (nums[mid] == nums[mid + 1]) {
                // Pair is aligned → single element is to the right
                left = mid + 2;
            } else {
                // Pair is broken → single element is at mid or left
                right = mid;
            }
        }
        
        return nums[left];
    }
}

Complexity Analysis

Time Complexity: O(log n)

At each step, we halve the search space (moving left to mid+2 or right to mid). After at most log₂(n) iterations, left and right converge. This satisfies the problem's O(log n) requirement.

Space Complexity: O(1)

We use only three integer variables (left, right, mid). No additional data structures. This satisfies the problem's O(1) space requirement.