Single Element in a Sorted Array
Problem link: https://leetcode.com/problems/single-element-in-a-sorted-array/
Problem Statement
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.
Input
A sorted integer array nums.
Output
The single integer that appears once.
Example
Input: nums = [1,1,2,3,3,4,4,8,8] Output: 2
Explanation
Before the '2', pairs start at even indices (0, 2). After the '2', pairs start at odd indices (4, 6).
Brute Force
Intuition
Traverse the array and compare each element with its neighbor. If an element doesn't have a matching neighbor, it's the single one.
Approach
- Iterate through the array with a step of 2.
- If nums[i] is not equal to nums[i+1], then nums[i] is the single element.
- If the loop ends, the last element is the single one.
Dry Run
nums = [1,1,2,3,3] i=0: nums[0]==nums[1] (1==1), continue. i=2: nums[2]!=nums[3] (2!=3), found 2!
Code (Java)
Complexity Analysis
We may potentially scan the entire array once.
Optimal Solution
Intuition
Use Binary Search. We need to find the 'partition' where the index pattern shifts from (even, odd) to (odd, even). If we are on an even index and the next element is the same, the single element is to the right.
Approach
- Initialize low = 0, high = nums.length - 2.
- While low <= high:
- Find mid. Ensure we check the pair property.
- A clever trick: If we use
mid = mid ^ 1, it toggles an even index to the next odd, and an odd index to the previous even. - If nums[mid] == nums[mid ^ 1], we are in the left half, move low = mid + 1.
- Otherwise, move high = mid - 1.
- Return nums[low].
Dry Run
nums = [1,1,2,3,3], low=0, high=3 Mid=1: nums[1]==nums[1^1] (nums[1]==nums[0]) is 1==1. low=2. Mid=2: nums[2]==nums[2^1] (nums[2]==nums[3]) is 2==3. false. high=1. Loop ends, return nums[low] which is 2.
Code (Java)
class Solution {
public int singleNonDuplicate(int[] nums) {
int low = 0, high = nums.length - 2;
while (low <= high) {
int mid = (low + high) / 2;
// The XOR trick checks the partner (even->next odd, odd->prev even)
if (nums[mid] == nums[mid ^ 1]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return nums[low];
}
}
Complexity Analysis
Binary search halves the search space in each step.
Quick Revision (Brute Force)
- Linear scan with step of 2
- Compare nums[i] with nums[i+1]
- O(N) time
Quick Revision (Optimal)
- Binary Search on index pairs
- Left of single: (Even, Odd) pairs
- Right of single: (Odd, Even) pairs
- Use mid ^ 1 trick to check partner
- O(log N) time