Distinct tracks in every k-play window

Scenario

Kestrel Stream runs auto-generated radio channels. Each channel picks its next track by itself, and the programming team checks how much variety it gives. A channel that loops the same few tracks loses listeners.

The team's measure is plain. Take every run of k consecutive plays on a channel and count how many different tracks played in it. The team wants one count for each run, from the first full run to the last, so they can plot variety across the day. Track ids are large numbers from the catalogue, and the same track can play several times in one run.

Your task

Write distinct_per_window(plays, k).

plays[i] is the track id of the play at position i on the channel, in order.
A window is k consecutive plays: plays[i] to plays[i + k - 1].
Return a list with one entry per window, in order of the start i. Each entry is the number of different track ids in that window.
The list has n - k + 1 entries, where n is the number of plays. k is never larger than n, so there is always at least one window.

Examples

Example 1 (traced)#

text2 lines

Input:  plays = [7, 3, 7, 7, 5, 3], k = 3
Output: [2, 2, 2, 3]

right	Joins	Leaves	Counts after the step	Keys in the map	Recorded
0	7	none	7→1	1	not yet
1	3	none	7→1, 3→1	2	not yet
2	7	none	7→2, 3→1	2	2
3	7	7	7→2, 3→1	2	2
4	5	3	7→2, 5→1	2	2
5	3	7	7→1, 5→1, 3→1	3	3

At position 3, one 7 joins and another 7 leaves, so nothing changes. At position 4, track 3 drops to zero and its key is deleted.

Example 2#

text2 lines

Input:  plays = [4, 4, 4, 4], k = 2
Output: [1, 1, 1]

A channel looping one track: every window holds one distinct track.

Example 3#

text2 lines

Input:  plays = [9, 2, 6, 2], k = 4
Output: [3]

When k equals the number of plays, there is one window. Track 2 plays twice but counts once.

Constraints

1 ≤ plays.length ≤ 10^5 (about 278 days of plays at 4 minutes a track)
1 ≤ plays[i] ≤ 10^9
1 ≤ k ≤ plays.length

What does n ≤ 10^5 tell you?

Building a new set for every window costs (n − k + 1) × k insertions. At n = 10^5 it peaks near k = 50,000, with about 2.5 × 10^9 insertions: far over the budget of about 10^8 simple operations a second. Aim for O(n).

The ids go up to 10^9, so you cannot use an array indexed by track id. Use a hash map from track id to its count in the window. It never holds more than k keys.

Scenario

Your task

Write distinct_per_window(plays, k).

plays[i] is the track id of the play at position i on the channel, in order.
A window is k consecutive plays: plays[i] to plays[i + k - 1].
Return a list with one entry per window, in order of the start i. Each entry is the number of different track ids in that window.
The list has n - k + 1 entries, where n is the number of plays. k is never larger than n, so there is always at least one window.

Examples

Example 1 (traced)#

text2 lines

Input:  plays = [7, 3, 7, 7, 5, 3], k = 3
Output: [2, 2, 2, 3]

right	Joins	Leaves	Counts after the step	Keys in the map	Recorded
0	7	none	7→1	1	not yet
1	3	none	7→1, 3→1	2	not yet
2	7	none	7→2, 3→1	2	2
3	7	7	7→2, 3→1	2	2
4	5	3	7→2, 5→1	2	2
5	3	7	7→1, 5→1, 3→1	3	3

At position 3, one 7 joins and another 7 leaves, so nothing changes. At position 4, track 3 drops to zero and its key is deleted.

Example 2#

text2 lines

Input:  plays = [4, 4, 4, 4], k = 2
Output: [1, 1, 1]

A channel looping one track: every window holds one distinct track.

Example 3#

text2 lines

Input:  plays = [9, 2, 6, 2], k = 4
Output: [3]

When k equals the number of plays, there is one window. Track 2 plays twice but counts once.

Constraints

1 ≤ plays.length ≤ 10^5 (about 278 days of plays at 4 minutes a track)
1 ≤ plays[i] ≤ 10^9
1 ≤ k ≤ plays.length

What does n ≤ 10^5 tell you?

The ids go up to 10^9, so you cannot use an array indexed by track id. Use a hash map from track id to its count in the window. It never holds more than k keys.