Distinct prices in every window

Question

For a price series and a window length k, report the number of distinct prices in each window of k consecutive ticks, as the window slides one tick at a time. Return the list of distinct-count values, one per window. Aim for O(n).

Accepted Answer

Maintain a count map of the prices currently inside the window. As the right edge advances by one, add the incoming price; once the window is full, remove the price leaving on the left, deleting its key when its count reaches zero so the map size always equals the number of distinct prices. Emit len(counts) once each full window is formed. Tracing [1, 1, 2, 3] with k = 2: window [1, 1] has one distinct value; [1, 2] and [2, 3] each have two, giving [1, 2, 2]. Time O(n), space O(k) for the window map. Deleting zero-count keys is essential, otherwise len(counts) would count prices that already …

Distinct prices in every window

Your answer

More Coding questions