Maximum number of unique integers

Question

I'm given N integers. I need to find the maximum number of unique integers among all the possible contiguous subarrays of size M.

Scanner in = new Scanner(System.in);
Deque deque = new ArrayDeque<Integer>();
int n = in.nextInt();
int m = in.nextInt();
in.nextLine();
String s = in.nextLine();
in.close();

int maxUnique = 0;
List<Integer> numbers = Stream.of(s.split(" "))
    .map(Integer::parseInt)
    .collect(Collectors.toList());
for (int i = 0; i <= n-m; i++) {
    HashSet<Integer> unique = new HashSet<>(numbers.subList(i, i+m));
    if (maxUnique < unique.size())
        maxUnique = unique.size();
    if (maxUnique == m) {
        System.out.println(maxUnique);
        return;
    }
}
System.out.println(maxUnique);

It works fine, but fails on big arrays due to timeout. For example N=100000, M=98777 times out.

How can I improve it?

Answer 1

You're almost there. You rebuild the entire HashSet for each of the i-m sub arrays resulting in (i-m)*m worrk.

Change the HashSet to a HashMap and then imagine the sub array as a sliding window. When the window moves one step to the right, count down number at the far left of the old window position in the HashMap and if it becomes zero, remove it. And then add the number to the far right of the new window position to the count of that number in the HashMap (or add the number with count one if it didn't exist), and at each window position take the size of the HashMap. This is (i-m)+m work which is much faster.