Official Editorial (C++)

Solution 1

Explanation

We can binary search for the largest valid segment size. If this segment is valid, update the current value of $\texttt{ret}$ with our indices $i$ and $j$. Rather than using a map, we instead opt to use a presized HashTable for faster $\mathcal{O}(1)$ query operations.

Implementation

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

Copy
 Code Snippet: C++ Short Template (Click to expand)

 Code Snippet: HashTable (Click to expand)

const int mx = 5e5 + 1;

int n, k;
int v[mx];
pi ret;

Solution 2

Explanation

Rather than binary searching for the maximum size, we can maintain a sliding window from $l$ to $r$. We only increment this window towards the right if two conditions hold:

1. $r<n-1$, meaning that we are not going out of bounds.
2. Adding $a[r+1]$ to the window doesn't increase the amount of different values to more than $k$.

We continue expanding towards the right until either of these conditions no longer hold. If our new segment is larger than the previous segment, we update the largest segment value.

Finally, we increment $l$, remove one occurrence of $a[l]$ from the frequency list, and update the number of different values.

Implementation

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

Copy
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9, MAX_Ai = 1e6 + 9;
int n, k;
int a[N];
int frequency[MAX_Ai];  // frequency of each number in the window
int maxSegment, leftMaxSegment,
    rightMaxSegment;  // max size of the segment and its ends

int main() {

Copy
import java.io.*;
import java.util.*;
public class KGood {
 	Code Snippet: Kattio (Click to expand)

	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int N = io.nextInt();
		int K = io.nextInt();
		int difVal = 0;  // Number of different values in the window.