DSA interview question

Single Element in a Sorted Array

Medium · Algorithms · Topics: binary search, array

The problem

A warehouse scanner logs every item twice (once in, once out), and the log is sorted by item ID. Exactly one item was scanned only once, a sign it was lost, and it must be found in O(log n), since the log is huge. XOR would find it in O(n), but sortedness enables better. Before the single element, each pair starts at an even index (0, 2, 4, ...); after it, every pair starts at an odd index. Binary search on that parity pattern pinpoints where it breaks.

Example: [1, 1, 2, 3, 3, 4, 4, 8, 8] → 2.

Function signature

int singleNonDuplicate(const vector<int>& nums);  // sorted; every value appears twice except one

Test cases

Input `nums`	Output	Explanation
`[1, 1, 2, 3, 3, 4, 4, 8, 8]`	2
`[3, 3, 7, 7, 10, 11, 11]`	10
`[1]`	1
`[1, 1, 2]`	2	The single is last
`[1, 2, 2]`	1	The single is first

(Confirm: the array is sorted, has odd length, and every value appears exactly twice except one; O(log n) time and O(1) space.)

How interviewers phrase it

"Find the single element in a sorted array where every other element appears twice, in O(log n)" (LeetCode 540).
Contrasted with the unsorted version (S.No 73), where XOR in O(n) is optimal.

Clarifying questions to ask

Is the array sorted?
Does every other value appear exactly twice?
Is O(log n) required? (Otherwise XOR is simpler.)

Follow-ups to expect

"What property are you searching on?"
"Why force mid to be even?"
"Why lo = mid + 2?"
"Why does the length have to be odd?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview