Single Element in a Sorted Array
Single Element in a Sorted Array is a medium binary search problem solved with the unique 1-d binary search pattern.
The best approach, optimal (binary search on pair alignment), runs in O(log n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from xor everything up.
Problem
In a sorted array, every value appears exactly twice except one value that appears once. Find it in O(log n) time and O(1) space.
Examples
Example 1
- Input
nums = [1, 1, 2, 3, 3, 4, 4]- Output
2
Example 2
- Input
nums = [5, 7, 7, 9, 9]- Output
5
Constraints
1 <= nums.length <= 10^5(always odd)- Every value appears twice except one. O(log n) time, O(1) space.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| XOR everything | O(n) | O(1) |
| Optimal (binary search on pair alignment) | O(log n) | O(1) |
1XOR everything
O(n)O(1)Pairs cancel under XOR, leaving the single value.
- x ^= each value; return x.
class Solution {
public int singleNonDuplicate(int[] nums) {
int x = 0;
for (int v : nums) x ^= v;
return x;
}
}class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
x = 0
for v in nums:
x ^= v
return xclass Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int x = 0;
for (int v : nums) x ^= v;
return x;
}
};function singleNonDuplicate(nums) {
let x = 0;
for (const v of nums) x ^= v;
return x;
}2Optimal (binary search on pair alignment)
O(log n)O(1)Look only at even indices mid. If nums[mid] == nums[mid + 1], the pairs are still aligned up to here, so the single element is to the right. Otherwise it is at mid or to the left.
- lo = 0, hi = n - 1.
- mid = lo + (hi - lo) / 2; if mid is odd, mid--.
- If nums[mid] == nums[mid + 1], lo = mid + 2; else hi = mid.
- Return nums[lo].
class Solution {
public int singleNonDuplicate(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mid % 2 == 1) mid--;
if (nums[mid] == nums[mid + 1]) lo = mid + 2;
else hi = mid;
}
return nums[lo];
}
}class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if mid % 2 == 1:
mid -= 1
if nums[mid] == nums[mid + 1]:
lo = mid + 2
else:
hi = mid
return nums[lo]class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mid % 2 == 1) mid--;
if (nums[mid] == nums[mid + 1]) lo = mid + 2;
else hi = mid;
}
return nums[lo];
}
};function singleNonDuplicate(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
let mid = lo + Math.floor((hi - lo) / 2);
if (mid % 2 === 1) mid--;
if (nums[mid] === nums[mid + 1]) lo = mid + 2;
else hi = mid;
}
return nums[lo];
}Edge cases to test
- The single value is first or last
- Length 1
Hints
Hint 1
Before the single element, pairs start at even indices. After it, they start at odd indices.
FAQ
What is the best time complexity for Single Element in a Sorted Array?
Optimal (binary search on pair alignment) runs in O(log n) time and O(1) extra space.
Which pattern does Single Element in a Sorted Array use?
It is a binary search problem that uses the unique 1-d binary search pattern. Other problems with the same pattern: First Bad Version, Find Peak Element.
Is there a brute force solution for Single Element in a Sorted Array?
Yes. XOR everything takes O(n) time and O(1) space. Pairs cancel under XOR, leaving the single value.
Which edge cases should I test for Single Element in a Sorted Array?
The single value is first or last; Length 1.