Single Element in a Sorted Array - Problem

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.

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

Input & Output

Example 1 — Single Element in Middle
$ Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
💡 Note: All elements appear twice except 2 which appears once. Element 2 is at index 2.
Example 2 — Single Element at Start
$ Input: nums = [3,3,7,7,10,11,11]
Output: 10
💡 Note: All elements appear twice except 10. Element 10 is at index 4.
Example 3 — Minimum Case
$ Input: nums = [1]
Output: 1
💡 Note: Only one element in array, so it must be the single element.

Constraints

  • 1 ≤ nums.length ≤ 105
  • 0 ≤ nums[i] ≤ 105
  • Array is sorted in ascending order
  • Every element appears exactly twice except one

Visualization

Tap to expand
Single Element in Sorted ArrayInput: [1,1,2,3,3,4,4,8,8]112334488012345678PairSinglePairPairPairPattern: Before single → pairs at (0,1), (2,3), after → pairs at (3,4), (5,6), (7,8)Single Element: 2Binary search uses this pattern to eliminate half the search space
Understanding the Visualization
1
Input
Sorted array with pairs and one single element
2
Pattern
Pairs normally start at even indices 0,2,4...
3
Output
Find the element that appears only once
Key Takeaway
🎯 Key Insight: The single element disrupts the even-odd pairing pattern, allowing binary search to efficiently locate it
Asked in
Facebook 25 Google 18 Amazon 15 Microsoft 12
182.0K Views
Medium Frequency
~15 min Avg. Time
3.4K Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen