Given n integers in input, consider each window in it sized m, where m is less or equal to n, and get the number of unique elements in each window. Return the maximum value among them.
This HackerRank Java Challenges problem is named
Java Dequeue, a clear hint that a Deque would helpful to solve it elegantly.
The HackerRank settings implies that data are passed us by System.in. To develop a method that could be easily tested, I made it accept an InputStream as parameter, then I passed it through a Scanner, in its own try-with-resource block.
public static int solution(InputStream is) {
try (Scanner scanner = new Scanner(is)) {
// ... see below
}
}
The first two integers we expect in the input stream are the above described n and m. A problem constrain states that m is not bigger than n, I make it clear in the code with an assertion.
int n = scanner.nextInt();
int m = scanner.nextInt();
assert m <= n;
Now I should be ready to get the next n integers and work on them. The big hint in the problem name suggests to push them in a Deque. Actually, we are going to use it as a queue. Since ArrayDeque is documented as "likely to be ... faster than LinkedList when used as a queue", my choice goes for it. To avoid slowdowns due to possible resizings, I create it specifying its capacity to the maximum "m" specified by the problem.
We also need to count the items in each window, and to do that a second container is useful. We'll push any item entering the window in a hash table, storing as value its current count. When an item exits the window we decrease its count in the hash. If the count is zero, we remove it.
We are going to call our method many times in a row, and I don't want to create each time a new deque and hash. It is cheaper to make them class data member, and simply reset them any time the method is called.
public class Solution {
private static final int MAX_WINDOW_SIZE = 100_000;
private static Deque<Integer> window = new ArrayDeque<>(MAX_WINDOW_SIZE);
private static Map<Integer, Integer> counter = new HashMap<>();
public static int solution(InputStream is) {
// ... see above
window.clear();
counter.clear();
// ... see below
}
}
Let's fill up the window for the first time. The hash map 'counter' is set up as described above.
for (int i = 0; i < m; i++) {
int in = scanner.nextInt();
window.add(in);
counter.merge(in, 1, Integer::sum);
}
int result = counter.size();
// ... see below
To count how many different integers are in the current window, I simply check the size of the hash map.
Now it is just a matter of iterating on all the other integer in the input stream.
for (int i = m; i < n && result < m; i++) {
Integer out = window.remove();
Integer in = scanner.nextInt();
window.add(in);
// ... see below
}
return result;
I have started looping on the m-th item, willing to go up to the n-th. But, wait, if I find a window with all different numbers (meaning, the current result is already equal to "m") I have already found the problem solution. That could save some CPU time.
In the loop, firstly I adjust the window, removing its first element and adding a new last element. The exiting and entering elements are used to modify the counter map. Then I recalculate the result, and I check it against the current solution.
if (out.intValue() != in.intValue()) { // 1
counter.merge(in, 1, Integer::sum); // 2
counter.merge(out, -1, (a, b) -> a == 1 ? null : a + b); // 3
result = Math.max(result, counter.size()); // 4
}
1. If what enters in the window is the same of what exists from it, I don't have to do anything.
2. I merge the item 'in' in the map. That means, if the map contains 'in', Integer::sum is used to adjust its value (on its current value and the '1' I passed in). Otherwise a new item is created in the map, key 'in', value '1'.
3. Similarly to the previous line, but now I'm performing a sort of 'merge down'. I'm not satisfied by this line I wrote, even though it is kind of fun. Its point is that we know for sure that 'out' is in the map, so we know that we are going to execute the lambda passed to merge(). It would return null if the value associated to 'out' is 1, removing it. Otherwise it would return a + b, but b is set to -1, so it would decrease it. The weak spot is, what if for 'out' is not in the map? Well, merge() would push it in, with value -1. Damn it. There is no way to avoid this inconsistency, since merge() would throw an exception if null is passed as value. End of the story is, I would not use this line in production code.
4. Maybe this check-and-set looks a bit too pythonic, what do you think about it?
Full Java code and test case available on GitHub.
Go to the full post
