Practice › Sliding Window
Shortest Window with K Distinct
Medium · Sliding Window
Find the length of the shortest contiguous subarray that contains at least k distinct values. Print -1 if no such subarray exists.
Input
First line: n. Second line: n integers. Third line: k.
Output
The minimum length, or -1.
Constraints
- 1 ≤ k ≤ n ≤ 10^5
- 1 ≤ a[i] ≤ 10^9
Example 1
Input
7 1 2 1 1 3 2 2 3
Output
3
Example 2
Input
3 4 4 4 2
Output
-1
Hints
- If a window already has ≥ k distinct values, making it longer never helps — try to shrink it from the left.
- Sliding window with a frequency map: extend the right end; while the map has ≥ k keys, record the length and remove the leftmost element.
Approach
Move r forward, adding a[r] to a frequency map. While the map has at least k keys, the window [l, r] qualifies: record r − l + 1, then remove a[l] (deleting its key when the count reaches 0) and advance l. Each index enters and leaves the window once, so this is O(n). If no window ever qualifies, which happens when the whole array has fewer than k distinct values, print -1.
Complexity: O(n) average time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
cin >> k;
unordered_map<long long, int> freq;
int best = INT_MAX, l = 0;
for (int r = 0; r < n; r++) {
freq[a[r]]++;
while ((int)freq.size() >= k) {
best = min(best, r - l + 1);
if (--freq[a[l]] == 0) freq.erase(a[l]);
l++;
}
}
cout << (best == INT_MAX ? -1 : best) << "\n";
return 0;
}Python solution
import sys
from collections import defaultdict
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, k = data[1 : n + 1], data[n + 1]
freq = defaultdict(int)
best, l = n + 1, 0
for r, x in enumerate(a):
freq[x] += 1
while len(freq) >= k:
best = min(best, r - l + 1)
freq[a[l]] -= 1
if freq[a[l]] == 0:
del freq[a[l]]
l += 1
print(-1 if best == n + 1 else best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
int k = sc.nextInt();
Map<Long, Integer> freq = new HashMap<>();
int best = Integer.MAX_VALUE, l = 0;
for (int r = 0; r < n; r++) {
freq.merge(a[r], 1, Integer::sum);
while (freq.size() >= k) {
best = Math.min(best, r - l + 1);
if (freq.merge(a[l], -1, Integer::sum) == 0) freq.remove(a[l]);
l++;
}
}
System.out.println(best == Integer.MAX_VALUE ? -1 : best);
}
}Solve Shortest Window with K Distinct online · All practice problems