1
\$\begingroup\$

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?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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++. \$\endgroup\$ May 26, 2018 at 1:54

1 Answer 1

5
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.