Practice › Sliding Window
Subarrays with K Different Integers
Hard · Sliding Window · Asked at Amazon, Google, Microsoft
Count the subarrays that contain exactly k different integers.
Input
First line: n k. Second line: n integers.
Output
The number of such subarrays.
Constraints
- 1 ≤ n ≤ 2 · 10^4
- 1 ≤ a[i], k ≤ n
exactly(k) = atMost(k) − atMost(k − 1). Counting subarrays with at most k distinct values is a standard sliding window.
Example 1
Input
5 2 1 2 1 2 3
Output
7
Example 2
Input
5 3 1 2 1 3 4
Output
3
Hints
- Counting "exactly k distinct" directly with one window is awkward, but "at most k distinct" is easy.
- exactly(k) = atMost(k) − atMost(k − 1).
Approach
atMost(k): slide a window with a frequency array and a distinct counter. Add a[r]; while distinct > k, remove a[l] and advance. Then all r − l + 1 subarrays ending at r with start ≥ l have at most k distinct values. Subtracting atMost(k − 1) leaves exactly those with k distinct values. Use 64-bit totals.
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
long long atMost(const vector<int> &a, int k) {
if (k < 0) return 0;
vector<int> cnt(a.size() + 2, 0);
long long res = 0;
int l = 0, distinct = 0;
for (int r = 0; r < (int)a.size(); r++) {
if (cnt[a[r]]++ == 0) distinct++;
while (distinct > k)
if (--cnt[a[l++]] == 0) distinct--;
res += r - l + 1;
}
return res;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &x : a) cin >> x;
cout << atMost(a, k) - atMost(a, k - 1) << "\n";
return 0;
}Python solution
import sys
def at_most(a, k):
if k < 0:
return 0
cnt = [0] * (len(a) + 2)
res = l = distinct = 0
for r, x in enumerate(a):
if cnt[x] == 0:
distinct += 1
cnt[x] += 1
while distinct > k:
cnt[a[l]] -= 1
if cnt[a[l]] == 0:
distinct -= 1
l += 1
res += r - l + 1
return res
data = list(map(int, sys.stdin.read().split()))
n, k, a = data[0], data[1], data[2:]
print(at_most(a, k) - at_most(a, k - 1))Java solution
import java.util.*;
public class Main {
static long atMost(int[] a, int k) {
if (k < 0) return 0;
int[] cnt = new int[a.length + 2];
long res = 0;
int l = 0, distinct = 0;
for (int r = 0; r < a.length; r++) {
if (cnt[a[r]]++ == 0) distinct++;
while (distinct > k)
if (--cnt[a[l++]] == 0) distinct--;
res += r - l + 1;
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
System.out.println(atMost(a, k) - atMost(a, k - 1));
}
}Solve Subarrays with K Different Integers online · All practice problems