Single Element in Sorted Array
MediumParity of indices points the way
Every number appears twice except one; use the pairs' positions to halve toward the lonely one.
The idea
Every element appears twice except one. Before the loner, a pair starts at an even index; after it, the pattern shifts — compare mid with its partner to pick a side.
1
1
2
3
3
4
4
8
8
0
1
2
3
4
5
6
7
8
Step 1 of 4. Brute force: values come in pairs — walk two at a time until a pair breaks. Values: 1, 1, 2, 3, 3, 4, 4, 8, 8.
1/4
Brute force
timeO(n)spaceO(1)
Walk pairs.
1let single = -1;2for (let i = 0; i < n && single < 0; i += 2)3 if (nums[i] !== nums[i + 1]) single = nums[i];4return single;Input
- array
- [1, 1, 2, 3, 3, 4, 4, 8, 8]
Memory
- i
- —
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
- Output:
- 2
- Explanation:
- Every value is doubled except 2.
Example 2
- Input:
- nums = [3, 3, 7, 7, 10, 11, 11]
- Output:
- 10
- Explanation:
- 10 stands alone.
Example 3
- Input:
- nums = [1]
- Output:
- 1
- Explanation:
- One element is the single.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.