Single Element in a Sorted Array solution and explanation
TCS
Google
9 more videos on this problem
Single element in a sorted array | Leetcode #540Techdose · 8:26 · 58K views
Single Element in a Sorted Array - Leetcode 540 - PythonNeetCodeIO · 10:44 · 35K views
Single Element in a Sorted Array | Amazon | Microsoft | Leetcode 540codestorywithMIK · 24:50 · 19K views
Leetcode | 540. Single Element in a Sorted Array | Medium | Java SolutionDeveloper Docs · 8:25 · 4K views
Single Element in a Sorted Array - Leetcode 540 - PythonTechError · 7:18 · 1K views
Leetcode 540. Single Element in a Sorted Array [Java]if else statement · 8:34 · 623 views
540. Single Element in a Sorted Array | JavaScript | Binary Search | LeetCode Daily ChallengeLeetCodeWithMonu · 13:05 · 442 views
540. Single Element in a Sorted Array | LeetCode MediumDeep Tech · 13:29 · 405 views
Daily Leetcode #1057: Feb 21, 2023 - 540. Single Element in a Sorted ArrayProgramming Live with Larry · 6:01 · 363 views
BS-8. Single Element in Sorted Arraytake U forward · 22:16 · 407K views
The 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.
Your solution must run 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 <= 1050 <= nums[i] <= 105
Approach overview
Problem Overview: You are given a sorted array where every element appears exactly twice except one element that appears once. The task is to return that single element. The sorted property creates a predictable pairing pattern that allows more efficient solutions than a full scan.
Approach 1: Bitwise XOR (O(n) time, O(1) space)
The simplest solution relies on the XOR property: a ^ a = 0 and a ^ 0 = a. Iterate through the array and XOR every value with an accumulator. Since every duplicated element cancels itself out, the final value left in the accumulator is the single element. This approach ignores the sorted nature of the array and works for any array where every number appears twice except one. Implementation is extremely short and constant space, but the runtime is linear because you must scan every element.
Approach 2: Binary Search (O(log n) time, O(1) space)
The optimal solution leverages the sorted structure of the array together with binary search. In a correctly paired array, elements appear in pairs where the first index is even and the second index is odd (e.g., [a,a,b,b,c,c]). Once the single element appears, this pairing pattern breaks. During binary search, check whether mid forms a valid pair with its neighbor. If mid is even and nums[mid] == nums[mid+1], the single element lies to the right; otherwise it lies to the left. If mid is odd, compare with nums[mid-1]. Each step discards half of the search space, reducing the runtime to logarithmic time.
The key insight is that the single element shifts the index parity of every pair after it. Binary search detects where that shift occurs. Because the array is sorted and duplicates are adjacent, each comparison immediately tells you which half of the array still follows the valid pairing structure.
Recommended for interviews: The binary search solution is what interviewers typically expect because it exploits the sorted property and achieves O(log n) time. The XOR approach is still useful to mention first—it demonstrates awareness of bitwise tricks and works in the general case—but the optimized binary search shows stronger algorithmic reasoning and pattern recognition.
Approach 1: Binary Search
This approach leverages the sorted property of the array to perform a binary search, achieving a time complexity of O(log n). The key observation is that elements are paired, except for the single unique element. Thus, we can use the middle index to determine if the unique element is in the left or right half of the array based on the pairing pattern.
def singleNonDuplicate(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if mid % 2 == 1:
mid -= 1
if nums[mid] == nums[mid + 1]:
left = mid + 2
else:
right = mid
return nums[left]
print(singleNonDuplicate([1, 1, 2, 3, 3, 4, 4, 8, 8]))class Solution {
public int singleNonDuplicate(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (mid % 2 == 1) mid--;
if (nums[mid] == nums[mid + 1]) {
left = mid + 2;
} else {
right = mid;
}
}
return nums[left];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 1, 2, 3, 3, 4, 4, 8, 8};
System.out.println(sol.singleNonDuplicate(nums));
}
}#include <vector>
#include <iostream>
using namespace std;
int singleNonDuplicate(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (mid % 2 == 1) mid--;
if (nums[mid] == nums[mid + 1]) {
left = mid + 2;
} else {
right = mid;
}
}
return nums[left];
}
int main() {
vector<int> nums = {1, 1, 2, 3, 3, 4, 4, 8, 8};
cout << singleNonDuplicate(nums) << endl;
return 0;
}function singleNonDuplicate(nums) {
let left = 0, right = nums.length - 1;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (mid % 2 == 1) mid--;
if (nums[mid] === nums[mid + 1]) {
left = mid + 2;
} else {
right = mid;
}
}
return nums[left];
}
console.log(singleNonDuplicate([1, 1, 2, 3, 3, 4, 4, 8, 8]));#include <stdio.h>
int singleNonDuplicate(int* nums, int numsSize) {
int left = 0, right = numsSize - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (mid % 2 == 1) mid--; // Ensures mid is even
if (nums[mid] == nums[mid + 1]) {
left = mid + 2;
} else {
right = mid;
}
}
return nums[left];
}
int main() {
int nums[] = {1, 1, 2, 3, 3, 4, 4, 8, 8};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", singleNonDuplicate(nums, size));
return 0;
}using System;
class Solution {
public int SingleNonDuplicate(int[] nums) {
int left = 0, right = nums.Length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (mid % 2 == 1) mid--;
if (nums[mid] == nums[mid + 1]) {
left = mid + 2;
} else {
right = mid;
}
}
return nums[left];
}
static void Main() {
Solution sol = new Solution();
int[] nums = {1, 1, 2, 3, 3, 4, 4, 8, 8};
Console.WriteLine(sol.SingleNonDuplicate(nums));
}
}The Python solution applies a binary search technique, adjusting the mid index to even and comparing elements to find the transition point between pairs, which is where the single element will be located.
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 2: Bitwise XOR
This approach exploits the properties of the XOR operation: a ^ a = 0 and a ^ 0 = a. We can XOR all elements, and since duplicates XOR to 0, only the unique element will remain.
def singleNonDuplicate(nums):
result = 0
for num in nums:
result ^= num
return result
print(singleNonDuplicate([3, 3, 7, 7, 10, 11, 11]))class Solution {
public int singleNonDuplicate(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {3, 3, 7, 7, 10, 11, 11};
System.out.println(sol.singleNonDuplicate(nums));
}
}#include <vector>
#include <iostream>
using namespace std;
int singleNonDuplicate(vector<int>& nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
int main() {
vector<int> nums = {3, 3, 7, 7, 10, 11, 11};
cout << singleNonDuplicate(nums) << endl;
return 0;
}function singleNonDuplicate(nums) {
let result = 0;
for (let num of nums) {
result ^= num;
}
return result;
}
console.log(singleNonDuplicate([3, 3, 7, 7, 10, 11, 11]));#include <stdio.h>
int singleNonDuplicate(int* nums, int numsSize) {
int result = 0;
for (int i = 0; i < numsSize; i++) {
result ^= nums[i];
}
return result;
}
int main() {
int nums[] = {3, 3, 7, 7, 10, 11, 11};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", singleNonDuplicate(nums, size));
return 0;
}using System;
class Solution {
public int SingleNonDuplicate(int[] nums) {
int result = 0;
foreach (int num in nums) {
result ^= num;
}
return result;
}
static void Main() {
Solution sol = new Solution();
int[] nums = {3, 3, 7, 7, 10, 11, 11};
Console.WriteLine(sol.SingleNonDuplicate(nums));
}
}The Python solution utilizes XOR to nullify paired elements, leaving the single unpaired element as the final result, a straightforward bit manipulation technique.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Binary Search
The given array nums is sorted, and we need to find the element that appears only once in O(log n) time. Therefore, we consider using binary search to solve this problem.
We define the left boundary of the binary search as l = 0 and the right boundary as r = n - 1, where n is the length of the array.
In each step, we take the middle position mid = (l + r) / 2. If the index mid is even, we should compare nums[mid] with nums[mid + 1]. If the index mid is odd, we should compare nums[mid] with nums[mid - 1]. Therefore, we can uniformly compare nums[mid] with nums[mid \oplus 1], where \oplus denotes the XOR operation.
If nums[mid] neq nums[mid \oplus 1], then the answer is in [l, mid], so we set r = mid. If nums[mid] = nums[mid \oplus 1], then the answer is in [mid + 1, r], so we set l = mid + 1. We continue the binary search until l = r, at which point nums[l] is the element that appears only once.
The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).
function singleNonDuplicate(nums: number[]): number {
let [l, r] = [0, nums.length - 1];
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] !== nums[mid ^ 1]) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l];
}func singleNonDuplicate(nums []int) int {
l, r := 0, len(nums)-1
for l < r {
mid := (l + r) >> 1
if nums[mid] != nums[mid^1] {
r = mid
} else {
l = mid + 1
}
}
return nums[l]
}impl Solution {
pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
let mut l = 0;
let mut r = nums.len() - 1;
while l < r {
let mid = (l + r) >> 1;
if nums[mid] != nums[mid ^ 1] {
r = mid;
} else {
l = mid + 1;
}
}
nums[l]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search | Time Complexity: O(log n) |
| Bitwise XOR | Time Complexity: O(n) |
| Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bitwise XOR | O(n) | O(1) | When the array may not be sorted or you want the simplest constant-space scan |
| Binary Search | O(log n) | O(1) | Best choice when the array is sorted and duplicates appear in pairs |
Frequently asked questions
Is Single Element in a Sorted Array easy or hard?
Single Element in a Sorted Array is rated Medium difficulty. The challenge is recognizing how the sorted pairing pattern changes after the single element and using that observation to adapt binary search.
Single Element in a Sorted Array Python/Java solution
Python and Java implementations usually follow the same binary search pattern: compute mid, check whether the pair structure is valid, and move the search boundaries accordingly. Both languages achieve O(log n) time and constant space with this approach.
How to solve Single Element in a Sorted Array in O(log n)?
Use binary search and observe the index parity of pairs. In a valid prefix of the array, the first occurrence of a pair appears at an even index and the second at an odd index. When this pattern breaks, the single element lies on that side of the array, allowing you to discard half the search space each step.
What is the best approach for Single Element in a Sorted Array?
Binary search is the best approach because the array is already sorted and duplicates appear in pairs. By checking whether the pairing pattern holds at the midpoint, you can discard half of the array each step. This reduces the runtime to O(log n) while using O(1) extra space.
Is Single Element in a Sorted Array asked at Google/Amazon/Meta?
Single Element in a Sorted Array frequently appears in coding interviews at companies like Google, Amazon, and Meta because it tests binary search variations and reasoning about sorted data structures. Interviewers often expect the O(log n) binary search solution rather than a linear scan.
What data structure is used in Single Element in a Sorted Array?
The problem primarily uses arrays along with the binary search algorithm. Some implementations also use bitwise XOR operations to cancel duplicate values when solving the problem with a linear scan.
What is the time complexity of Single Element in a Sorted Array?
The optimal binary search solution runs in O(log n) time with O(1) space. A simpler XOR-based scan takes O(n) time and O(1) space because it processes every element in the array.