Log inSign up
mediumLeetCodeNot Started

Single Element in a Sorted Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 · Single Element in Middle:

Input: nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
Output: 2
Explanation: 2 appears only once while 1, 3, 4, 8 appear twice.

Example 2 · Single Element at End:

Input: nums = [3, 3, 7, 7, 10, 11, 11]
Output: 10
Explanation: 10 appears only once.

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105
  • All integers appear twice except for one which appears once.
  • nums is sorted in non-decreasing order.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Binary Search boundary conditions
  • Bitwise XOR parity properties
  • Index arithmetic and pair grouping

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Leverage sorted index parity invariants in binary search.
  • Formulate XOR indexing (mid ^ 1) for pair partner lookup.
  • Implement low < high convergence for singleton searches.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • Check mid parity: if mid is odd, mid--.
  • If nums[mid] == nums[mid + 1] -> low = mid + 2.
  • Else -> high = mid.

Connected Patterns:

Single Number I / II / IIIFind Peak Element

1. Bitwise XOR Reduction (Brute Force)

Intuition

By identity: x ^ x = 0 and x ^ 0 = x. Taking the XOR accumulator of the entire array cancels out every duplicate pair, leaving the single isolated element in O(n) time and O(1) space.

When to apply: Use to understand the parity cancellation property before exploiting sorted order.

Linear Frequency Counting (O(N) Time, O(N) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Elements with frequency 2 are normal pairs
Visual state
Values and pointers at this exact step
pointers
S
1
1
2
3
3
4
4
8
8
0
↑ i
1
2
3
4
5
6
7
8
Variables at this step
currentVal
1
count
2
freqMap
{"1":2}
Check / comparison
Process element 1: appears at indices 0 and 1
Decision / next transition
freq[1] = 2. It is paired; continue.
Why this step matters

Elements with frequency 2 are normal pairs.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int singleNonDuplicate(int[] nums) {
4 int xor = 0;
5 for (int x : nums) xor ^= x;
6 return xor;
7 }
8 }
9
10 public static void main(String[] args) {
11 Solution sol = new Solution();
12 int[] nums = {1, 1, 2, 3, 3, 4, 4, 8, 8};
13 System.out.println("Single Element: " + sol.singleNonDuplicate(nums));
14 }
15}

Time & Space Complexity

  • Time complexity: O(n) — A single linear pass XORing all n numbers.
  • Space complexity: O(1) — O(1) memory for the XOR accumulator.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Linear Step-by-2 Scan (Better)

Intuition

Since pairs normally occupy (even, odd) positions (0,1), (2,3)..., we step by 2: i = 0, 2, 4... If nums[i] != nums[i + 1], then nums[i] is the single element that broke the pattern.

When to apply: Use to verify the adjacent pair alignment property before applying binary search.

Bitwise XOR Accumulation (O(N) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Identical numbers cancel each other out bitwise
Visual state
Values and pointers at this exact step
pointers
S
1
1
2
3
3
4
4
8
8
0
1
↑ xor
2
3
4
5
6
7
8
Variables at this step
xorAcc
0
processedIdx
1
Check / comparison
XOR pair (1, 1): 0 ^ 1 ^ 1 = 0
Decision / next transition
Accumulator is 0. Pair cancels completely.
Why this step matters

Identical numbers cancel each other out bitwise.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int singleNonDuplicate(int[] nums) {
4 for (int i = 0; i < nums.length - 1; i += 2) {
5 if (nums[i] != nums[i + 1]) return nums[i];
6 }
7 return nums[nums.length - 1];
8 }
9 }
10
11 public static void main(String[] args) {
12 Solution sol = new Solution();
13 int[] nums = {1, 1, 2, 3, 3, 4, 4, 8, 8};
14 System.out.println("Single Element: " + sol.singleNonDuplicate(nums));
15 }
16}

Time & Space Complexity

  • Time complexity: O(n) — At most n/2 pair comparisons.
  • Space complexity: O(1) — O(1) memory.

3. Binary Search on Even Indices (Optimal)

Intuition

1. All pairs before the single element start at even indices (even, odd). 2. All pairs after the single element start at odd indices (odd, even). 3. Therefore, if mid is even and nums[mid] == nums[mid + 1], the single element must be strictly to the right: low = mid + 2. 4. If nums[mid] != nums[mid + 1], the disruption is at mid or to the left: high = mid. 5. When low == high, nums[low] is the unique element.

When to apply: Use as the optimal O(log n) time and O(1) space solution required by the problem prompt.

Binary Search on Even Indices (O(log N) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Before the single element, nums[even] == nums[even+1]
Visual state
Values and pointers at this exact step
pointers
S
1
1
2
3
3
4
4
8
8
0
↑ low
1
2
3
4
↑ mid
5
6
7
8
↑ high
Variables at this step
low
0
mid
4
high
8
isEven
true
Check / comparison
low = 0, high = 8 -> mid = 4 (even). Compare nums[4] (3) with nums[5] (4)
Decision / next transition
nums[4] != nums[5]. Pair alignment is broken! Single element is at or left of mid. Set high = mid = 4.
Why this step matters

Before the single element, nums[even] == nums[even+1]. Since nums[4] != nums[5], the disruption occurred at or before index 4.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int singleNonDuplicate(int[] nums) {
4 int low = 0, high = nums.length - 1;
5 while (low < high) {
6 int mid = low + (high - low) / 2;
7 if (mid % 2 == 1) mid--;
8 if (nums[mid] == nums[mid + 1]) {
9 low = mid + 2;
10 } else {
11 high = mid;
12 }
13 }
14 return nums[low];
15 }
16 }
17
18 public static void main(String[] args) {
19 Solution sol = new Solution();
20 int[] nums = {1, 1, 2, 3, 3, 4, 4, 8, 8};
21 System.out.println("Single Element: " + sol.singleNonDuplicate(nums));
22 }
23}

Time & Space Complexity

  • Time complexity: O(log n) — The search space halves on each step, taking ceil(log2(n)) comparisons.
  • Space complexity: O(1) — O(1) auxiliary pointer variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear Scan Pair CheckingO(N)O(1)Step by 2: if nums[i] != nums[i+1], return nums[i].Scans entire array.
2.Better — Bitwise XOR AccumulationO(N)O(1)XOR all elements together; matching pairs cancel to 0, leaving the single element.Inspects all N elements.
3.Optimal — Binary Search on Index ParityOptimalO(log N)O(1)Bisect on even indices checking if nums[mid] == nums[mid + 1].Optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Single Element in a Sorted Array?

2.Why is the brute force approach suboptimal for large inputs in Single Element in a Sorted Array?

3.Which data structure or technique enables the optimal solution for Single Element in a Sorted Array?

Back to DSA Sheet