Editorial for K-Distinct Windows

Use this editorial only when stuck, and do not copy-paste code from it.

Please be respectful to the problem author and editorialist. Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Maintain the frequency of each value inside the current window of length $x$ , together with the number of distinct values currently present.

Build the first window, check whether it contains at least $k$ distinct values, then slide the window one position at a time:

remove the value leaving the window;
add the value entering the window;
update the distinct counter whenever a frequency changes between $0$ and $1$ .

Each slide takes $O(1)$ , so the full scan runs in $O(n)$ time.

Solution (Python)

Code 1

from collections import defaultdict


n, x, k = map(int, input().split())
values = list(map(int, input().split()))

freq: dict[int, int] = defaultdict(int)
distinct = 0

for i in range(x):
    if freq[values[i]] == 0:
        distinct += 1
    freq[values[i]] += 1

answer = 1 if distinct >= k else 0

for right in range(x, n):
    left_value = values[right - x]
    freq[left_value] -= 1
    if freq[left_value] == 0:
        distinct -= 1

    if freq[values[right]] == 0:
        distinct += 1
    freq[values[right]] += 1

    if distinct >= k:
        answer += 1

print(answer)

Comments0

No comments yet

Be the first to comment.

Editorial for K-Distinct Windows

Approach

Solution (Python)

Comments0

New comment