Single Element in a Sorted Array
MedPrompt
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: 2Example 2:
Input: nums = [3,3,7,7,10,11,11]
Output: 10
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves iterating through the sorted array and comparing adjacent elements. Since every element appears twice except for one, the pairs of identical numbers will be next to each other. We can check elements in pairs to find the one that breaks the pattern.
Algorithm
- Iterate through the array from index 0 to
n-2with a step of 2. - At each step
i, comparenums[i]andnums[i+1]. - If
nums[i] != nums[i+1], thennums[i]is the unique element. Return it. - If the loop finishes, the last element
nums[n-1]is the unique one. Return it.
Walkthrough
The algorithm iterates through the array with a step of 2. For each index i, it compares nums[i] with nums[i+1]. If they are different, nums[i] must be the single element because all preceding elements formed valid pairs. If the loop completes, the single element must be the last one in the array.
class Solution { public int singleNonDuplicate(int[] nums) { // Handle the edge case of a single element array if (nums.length == 1) { return nums[0]; } // Iterate through the array by pairs for (int i = 0; i < nums.length - 1; i += 2) { // If a pair doesn't match, the first element is the single one if (nums[i] != nums[i + 1]) { return nums[i]; } } // If the loop finishes, the single element is the last one return nums[nums.length - 1]; }}Complexity
Time
O(n) - In the worst-case scenario, we might have to traverse the entire array to find the single element (e.g., when it's the last element).
Space
O(1) - We only use a constant amount of extra space for loop variables.
Trade-offs
Pros
Very simple to understand and implement.
Cons
Inefficient for large inputs.
Does not meet the O(log n) time complexity requirement specified in the problem.
This clever approach uses the properties of the bitwise XOR operator. XORing a number with itself results in 0 (a ^ a = 0), and XORing a number with 0 leaves the number unchanged (a ^ 0 = a). By XORing all numbers in the array, all the duplicate pairs will cancel each other out, leaving only the single, non-duplicated element.
Algorithm
- Initialize a variable
resultto 0. - Iterate through each number
numin the input arraynums. - Update
resultby XORing it with the current number:result = result ^ num. - After the loop,
resultwill contain the single non-duplicate element. Returnresult.
Walkthrough
We initialize a variable, say uniqueElement, to 0. Then, we iterate through the nums array. In each iteration, we perform a bitwise XOR operation between uniqueElement and the current number, and store the result back in uniqueElement. After the loop, uniqueElement will hold the value of the single number that appears only once.
class Solution { public int singleNonDuplicate(int[] nums) { int uniqueElement = 0; for (int num : nums) { uniqueElement ^= num; } return uniqueElement; }}Complexity
Time
O(n) - We must iterate through every element in the array once.
Space
O(1) - Only a single integer variable is used to store the cumulative XOR result.
Trade-offs
Pros
Elegant and concise.
Works even if the array is not sorted.
Cons
Does not utilize the sorted property of the array.
Fails to meet the O(log n) time complexity requirement.
The most efficient approach leverages the fact that the array is sorted. We can use binary search to find the single element in logarithmic time. The core idea is to observe the indices. Before the single element, every pair (nums[i], nums[i+1]) starts at an even index i. After the single element, this pattern is disrupted, and pairs start at an odd index. We can use this property to decide which half of the array to search next.
Algorithm
- Initialize search boundaries
low = 0andhigh = nums.length - 1. - Loop while
low < high. - Calculate
mid = low + (high - low) / 2. - To ensure we are always looking at the start of a pair, if
midis odd, adjust it:mid--. - Check if the pair at
(mid, mid+1)is a valid pair (nums[mid] == nums[mid+1]). - If it is a valid pair, the single element must be in the right half. Set
low = mid + 2. - If it is not a valid pair, the single element is in the left half (including
mid). Sethigh = mid. - When the loop terminates (
low == high),nums[low]is the single element. Return it.
Walkthrough
We perform a binary search on the array indices. Let low = 0 and high = n-1. In each step, we calculate mid. We need to check the element at mid and its pair. To simplify, we can ensure mid is always an even index. If mid is odd, we decrement it by one. Now, we compare nums[mid] and nums[mid+1].
- If
nums[mid] == nums[mid+1], it means the array up tomid+1is 'correct' (all elements form pairs), so the single element must be in the right half. We updatelow = mid + 2. - If
nums[mid] != nums[mid+1], it means the disruption (the single element) is in the left half (includingmid). We updatehigh = mid. The loop continues untillowandhighconverge, at which pointnums[low]is our answer.
class Solution { public int singleNonDuplicate(int[] nums) { int low = 0; int high = nums.length - 1; while (low < high) { int mid = low + (high - low) / 2; // We want to check pairs, so we need to ensure mid is at an even index. // If mid is odd, its pair is at mid-1. If mid is even, its pair is at mid+1. // Let's make mid always point to the first element of a pair. if (mid % 2 == 1) { mid--; } // If the elements at mid and mid+1 are the same, it means the single element // is not in the left part (including mid and mid+1). So we search on the right. if (nums[mid] == nums[mid + 1]) { low = mid + 2; } // If they are different, the single element is in the left part (including mid). else { high = mid; } } // When low == high, we have found the index of the single element. return nums[low]; }}Complexity
Time
O(log n) - Standard binary search halves the search space in each iteration.
Space
O(1) - No extra space proportional to the input size is used.
Trade-offs
Pros
Extremely efficient, meeting the problem's time and space constraints.
Effectively uses the sorted property of the array.
Cons
The logic is more complex to devise and implement correctly compared to linear scans.
Solutions
Solution
class Solution {public int singleNonDuplicate(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = (left + right) >> 1;class Solution {public: int singleNonDuplicate(vector<int> &nums) { int left = 0, right = nums.size() - 1; while (left < right) { int mid = left + right >> 1; if (nums[mid] != nums[mid ^ 1]) right = mid; else left = mid + 1; } return nums[left]; }};class Solution : def singleNonDuplicate ( self , nums : List [ int ]) -> int : left , right = 0 , len ( nums ) - 1 while left < right : mid = ( left + right ) >> 1 # Equals to: if (mid % 2 == 0 and nums[mid] != nums[mid + 1]) or (mid % 2 == 1 and nums[mid] != nums[mid - 1]): if nums [ mid ] != nums [ mid ^ 1 ]: right = mid else : left = mid + 1 return nums [ left ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.