Extracting Unique Elements from a Sorted Array

This question is about processing a sorted array to extract the distinct values in order, producing a compact representation of its unique elements. The candidate is asked to exploit the fact that the data is already ordered, and to design an implementation that walks the sequence once and decides which entries to keep. Variants of this pattern appear in basic data-cleaning pipelines, deduplication tasks, and as a building block in more complex algorithms where sortedness is guaranteed by upstream logic or data structures.

It leans on ideas from linear-time array scans, index-based iteration, and careful use of comparisons between neighboring elements. An interviewer is watching for recognition that sortedness is the key structural property and that no auxiliary data structure is required for correctness. They look at how the candidate handles edge cases such as empty or single-element inputs, and whether the code is clear, efficient, and avoids off-by-one errors. For more experienced roles, they may probe in-place variants and memory–time trade-offs.

What it tests

When working with a sorted sequence, the key structural property is that all duplicate values are grouped together in contiguous blocks. This means that any transition from one value to another in the sequence marks the boundary between different unique elements. The underlying pattern is that uniqueness can be detected by comparing each element to its immediate predecessor: a change indicates a new unique value. This approach leverages the order to avoid the need for extra bookkeeping or hash sets, which would be necessary in an unsorted context. The reason this works is that sorting imposes a total order, collapsing all duplicates into adjacent positions, making their detection a simple linear scan.