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: 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 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