Getting everything ready for you…

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

0s

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

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

  1. If a window already has ≥ k distinct values, making it longer never helps — try to shrink it from the left.
  2. 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