# Maximum number of unique integers

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?

• Use a data structure to store values of the numbers you find. Like if the first number is 876, store it. If you find it again, raise it's counter. You can use direct access container like a dynamic array(we call them vectors in C++), but it's minimum size will be n - meaning it will take space, then you can find out maximum and minimum in O(logn) time using another algorithm. It would be easier to use a hash table. I would use vector of pairs in C++. – Aniket Chowdhury May 26 '18 at 1:54