Skip to content

Removing repeats from a sorted array

Question

An array is sorted in increasing order and may contain repeated values. How do you extract the list of distinct values?

Short answer

One pass comparing each element with the previous one: O(n)O(n) time. Because equal values sit next to each other, keep an element only when it differs from the last value kept. It can be done in place with a write index, using O(1)O(1) extra space.

Adapted from Zhou, A Practical Guide to Quantitative Finance Interviews, sec. 7.1 Algorithms, 'Unique elements', p.172; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question