Single Element in a Sorted Array — Problem & Solution
Single Element in a Sorted Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Single Element in a Sorted Array is a medium coding problem on arrays and binary search, asked in Zomato interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search
- Asked at: Zomato
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a sorted array where every element appears exactly twice, except one element that appears once. Return that single element in O(log n) time and O(1) space.
Example 1
Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2
Input: nums = [3,3,7,7,10,11,11]
Output: 10
Constraints
1 <= nums.length <= 31 (odd)0 <= nums[i] <= 100Sorted; every value twice except one.
Hints for Single Element in a Sorted Array
Hint 1
Before the single element, pairs start at even indices; after it, they start at odd indices.
Hint 2
Binary search on that parity flip.
How to solve Single Element in a Sorted Array
Pairing gives the array a hidden structure. Before the lone element, every pair starts at an even index; after it, the pairing is shifted and pairs start at odd indices. That parity flip happens exactly at the single element, and a binary search can hunt for it.
Approach
- Search a range
[lo, hi]over indices, looping whilelo < hi. - Take
mid, and if it is odd, step it down by one so it always points at a potential pair start. - If
nums[mid] == nums[mid + 1], the pairing is still intact here — the single element is further right, solo = mid + 2. - Otherwise the pairing has already broken — the single element is at
midor before it, sohi = mid. - When the range collapses,
nums[lo]is the answer.
Why it works
Left of the unique element the array is a perfect sequence of pairs on even boundaries, so nums[even] == nums[even + 1] holds throughout. From the unique element onwards everything shifts by one, so that equality fails. Forcing mid to be even makes the test a direct probe of which side of the flip you are on, and since the flip point is unique the predicate is monotone — exactly what binary search needs.
Complexity
- Time —
O(log n) - Space —
O(1)
Pitfalls
- Round
middown to even before comparing; testing an odd index inverts the meaning of the result. - Advance by
mid + 2on a matched pair — skipping a whole pair is the point. - Use
hi = midso the candidate stays in range. - The array length is always odd, and both the first and last position are valid answers.
Reference solution
Python
from typing import List
def singleNonDuplicate(nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if mid % 2 == 1:
mid -= 1
if nums[mid] == nums[mid + 1]:
lo = mid + 2
else:
hi = mid
return nums[lo]Java
public static 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];
}C++
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];
}JavaScript
var singleNonDuplicate = function(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
let mid = (lo + hi) >> 1;
if (mid % 2 === 1) mid--;
if (nums[mid] === nums[mid + 1]) lo = mid + 2;
else hi = mid;
}
return nums[lo];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search