Explanation

We can use a sliding window to keep track of the MM elements that cannot be excluded. To track the excluded elements, we can store all integers from 00 to NN in a set and report the lowest value in the set for each window. A frequency table is used to track the number of instances of an element in the window in order to determine when it must be removed or added from the excluded set.

Implementation

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

C++

#include <climits>
#include <iostream>
#include <set>
#include <vector>


using namespace std;


int main() {
	int n, m;
	cin >> n >> m;

Java

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


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());


		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

Python

Warning!

This solution TLEs even with PyPy.

from bisect import bisect_left, insort


n, m = map(int, input().split())
arr = list(map(int, input().split()))


s = list(range(n + 1))
present = [True] * (n + 1)
window_freq = [0] * (n)
res = float("inf")

Alternate Solution

We can make an observation that eliminates the need to actually keep track of the window. An element can be excluded from the window for two reasons:

  • There is a gap of at least size MM between two instances of the same number.
  • The element does not appear at all.

Thus, we can keep track of the last seen position of every element and determine if there is ever a gap of size MM between the two positions. After, we can compare each last seen position with the endpoint both to check for distance from the end and also existence.

Implementation

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

C++

#include <iostream>
#include <vector>
using namespace std;


int main() {
	int n, m;
	cin >> n >> m;


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

Java

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


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nm = br.readLine().split(" ");
		int n = Integer.parseInt(nm[0]);
		int m = Integer.parseInt(nm[1]);

Python

n, m = map(int, input().split())
nums = list(map(int, input().split()))


last_seen_pos = [-1] * (n + 1)
valid = [False] * (n + 1)


for i in range(n):
	if i - last_seen_pos[nums[i]] > m:
		valid[nums[i]] = True
	last_seen_pos[nums[i]] = i

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