Compact a sorted price ladder in place

Question

A price ladder arrives as a sorted (non-decreasing) list, but some levels repeat. Overwrite the array in place so the first part holds each distinct price once, in order, and return how many distinct prices there are. Elements past that length may hold anything.

prices = [10, 10, 11, 12, 12]
-> 3   with prices[:3] == [10, 11, 12]

Compact the sorted array in place and return the count of distinct values. Aim for $O(n)$ time, $O(1)$ space.

Accepted Answer

Use a slow write pointer w and a fast read pointer r. w marks how many distinct values have been committed; the last committed value sits at prices[w - 1]. For each r, if prices[r] differs from that last committed value, it is new, so write it at prices[w] and advance w. Tracing [10, 10, 11, 12, 12]: the second 10 is skipped, 11 and 12 are each written once, and duplicates of 12 are skipped. w ends at 3 with the front being [10, 11, 12]. Time O(n), space O(1). Edge cases: an empty list returns 0, and a list with no duplicates returns its own length unchanged. The comparison against prices[w -…

Compact a sorted price ladder in place

Your answer

More Coding questions