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.
Solutions
Solution
class Solution {public int singleNonDuplicate(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = (left + right) >> 1;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.