Single Element in a Sorted Array

Single Element in a Sorted Array

What is this problem about?

In the "Single Element in a Sorted Array" interview question, you are given a sorted array where every element appears exactly twice, except for one element which appears only once. Your goal is to find this unique element in O(log n) time complexity. This "Single Element in a Sorted Array coding problem" is a variation of finding an element in a sorted list but with a twist involving parity and pairs.

Why is this asked in interviews?

Tech giants like Microsoft, Meta, and Amazon ask this because it tests if you can move beyond simple linear scans. While finding the unique element is trivial in O(n) time using a loop or XOR, achieving O(log n) requires a deep understanding of Binary Search. It challenges you to identify the specific property of the sorted array that allows you to discard half of the search space at each step.

Algorithmic pattern used

This is a sophisticated "Binary Search interview pattern". In a perfectly paired array, pairs start at even indices (0, 2, 4...). When a single element is introduced, it shifts the parity of all subsequent pairs. To solve this, you use binary search:

• If the middle index mid is even and nums[mid] == nums[mid + 1], the single element must be to the right.
• If mid is even and nums[mid] != nums[mid + 1], the single element is either at mid or to the left. By checking the relationship between the index parity and the values of neighbors, you can narrow down the unique element's location.

Example explanation

Array: [1, 1, 3, 3, 4, 5, 5, 7, 7]

• Indices: 0, 1, 2, 3, 4, 5, 6, 7, 8

1. low=0, high=8, mid=4.
2. nums[4] is 4. Neighbors are 3 and 5.
3. Since mid is 4 (even) and nums[4] != nums[5], the "broken" pair is at or before index 4. Set high=4.
4. low=0, high=4, mid=2.
5. nums[2] is 3. mid is 2 (even), and nums[2] == nums[3]. This means everything to the left is paired correctly. Set low=mid+2=4.
6. low=4, high=4. Found it! The element at index 4 is 4.

Common mistakes candidates make

The most common error is providing an O(n) solution (like XORing all elements) when the interviewer specifically asks for O(log n). Another mistake is messy index handling during the binary search, leading to infinite loops or out-of-bounds errors. Candidates also struggle with the logic of which side to move to based on the mid index parity, which is the crux of the "Single Element in a Sorted Array interview question".

Interview preparation tip

Whenever you see a "Sorted Array" and a requirement for a time complexity better than O(n), your first thought should always be Binary Search. Practice variations where the search condition is not a direct value match but a property change (like parity shift). This will help you tackle more complex "HARD" level binary search problems.