Find the Unique Element in Pairs
Company: Xiaohongshu
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Quick Answer: This question evaluates a candidate's ability to design time- and space-efficient algorithms for sorted array problems, focusing on identifying a single non-duplicated element among paired values.
Constraints
- 1 <= nums.length <= 100000
- nums.length is odd
- The array is sorted in nondecreasing order
- Exactly one element appears once; every other element appears exactly twice
Examples
Input: ([1,1,2,3,3,4,4,8,8],)
Expected Output: 2
Explanation: All numbers appear twice except `2`, so the answer is 2.
Input: ([3,3,7,7,10,11,11],)
Expected Output: 10
Explanation: The only value that does not have a matching pair is 10.
Input: ([5],)
Expected Output: 5
Explanation: A single-element array means that element is the unique one.
Input: ([0,1,1,2,2,3,3],)
Expected Output: 0
Explanation: The unique value appears at the beginning of the array.
Input: ([1,1,2,2,9],)
Expected Output: 9
Explanation: The unique value appears at the end of the array.
Hints
- Before the unique element, pairs start at even indices. After the unique element, that pattern shifts.
- During binary search, force `mid` to be even and compare `nums[mid]` with `nums[mid + 1]`.