Solution: Subarray Distinct Values | Sliding Window

Explanation

Use a sliding window and keep a multiset to record the frequency of each element in the array. Expand the window to the right if the number of distinct elements after expanding the window is less or equal to $K$ , otherwise remove the left-most element. When a new element at index $i$ is added to a window with a left-most element of index $j$ , it will create ( $i - j$ ) new subarrays, i.e ( $j$ to $i$ ), ( $j + 1$ to $i$ ), etc. which we can use to calculate the number of valid subarrays.

Implementation

Time Complexity: $\mathcal{O}(N)$

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
	int n;
	int k;
	cin >> n >> k;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) { cin >> arr[i]; }

Java

import java.io.*;
import java.util.*;

public class cses2428 {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int N = io.nextInt();
		int K = io.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) { arr[i] = io.nextInt(); }

Python

n, k = map(int, input().split())
arr = list(map(int, input().split()))
left = 0
right = 0
ans = 0
distinct = 0
freq = {}
while left < n:
	while right < n:
		if arr[right] not in freq and distinct == k:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum

Table of Contents

Table of Contents

Explanation

Implementation

Join the USACO Forum!