Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Counting "exactly k distinct" directly with one window is awkward, but "at most k distinct" is easy.
  2. 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