Java - Select the maximum integers from sliding windows over an array

Question

So I have the following algorithm. Given an array A[0 ... n - 1] and the window length w, compute all the windows A[0 ... w - 1], A[1 ... w], ..., A[n - w, n - 1], and for each window, in order, compute the maximum integer in the window, storing it in a result array:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
public class Main {
 private static final int[] EMPTY_INT_ARRAY = new int[0];
 public static void main(String[] args) {
 int[] array = {7, 86, 19, 5, 79, 28, 56, 8, 46, 63, 98, 65, 99};
 int[] result = computeArrayWindowMaxima(array, 8);
 System.out.println(Arrays.toString(array));
 System.out.println(Arrays.toString(result));
 System.out.println();
 array = new int[]{1, 100, 2, 100, 4, 5, 6, 7};
 result = computeArrayWindowMaxima(array, 4);
 System.out.println(Arrays.toString(array));
 System.out.println(Arrays.toString(result));
 }
 public static int[] computeArrayWindowMaxima(int[] array, 
 int windowLength) {
 Objects.requireNonNull(array, "The input array is null.");
 if (array.length == 0) {
 return EMPTY_INT_ARRAY;
 }
 // Let n = array.length, m = windowLength.
 windowLength = Math.min(windowLength, array.length);
 int[] result = new int[array.length - windowLength + 1];
 OrderStatisticTree<Integer> tree = new OrderStatisticTree<>();
 Map<Integer, Integer> counterMap = new HashMap<>();
 // Initialize the tree. Runs in O(m log m):
 for (int i = 0; i < windowLength; ++i) {
 tree.add(array[i]);
 counterMap.put(array[i],
 counterMap.getOrDefault(array[i], 0) + 1);
 }
 // Runs in O((n - m) log m).
 for (int i = 0; i < result.length - 1; ++i) {
 // Store tree window maximum. Runs in O(log m).
 result[i] = tree.get(tree.size() - 1);
 // Remove the int right before the current window. Runs in
 // O(log m).
 if (counterMap.getOrDefault(array[i], 0) < 2) {
 counterMap.remove(array[i]);
 tree.remove(array[i]);
 } else {
 counterMap.put(array[i], counterMap.get(array[i]) - 1);
 }
 // Add the int right after the current window. Runs in O(log m).
 tree.add(array[windowLength + i]);
 counterMap.put(array[windowLength + i],
 counterMap.getOrDefault(
 array[windowLength],
 0)
 + 1);
 }
 result[result.length - 1] = tree.get(tree.size() - 1);
 // Finally, we have O(m \log m) + O((n - m) log m) = O(n log m).
 return result;
 }
}

In the above procedure, tree [1] holds the current window and the counterMap is used to count the number of times each int in the window occurs in that window. We need counterMap since it is possible that multiple maximum ìnts belong to a window and removing one will "remove all duplicates", so to say.

Critique request

Now, what do you think? As always, tell me whatever comes to mind.

[1] Order statistic tree.

• greybeard: There is at least one slick O(n) algorithm. Looking for a collection that supports add(key), remove(key) & maxKey() fast is barking up the wrong tree.
• coderodde: @greybeard geeksforgeeks.org/…. And all of a sudden, the problem turned out to be boring.
• greybeard: I guess it's interesting as an interview question: If the interviewee doesn't seem to remember problem&solution, s/he's bound to fall into the PQ trap. The interesting part is the reaction confronted with the interviewer's asking for/asserting there is a straightforward O(n) solution.
• coderodde: @greybeard Beyond my level.

Answer 1

There may be avoidable overhead in finding the same key in a Map twice in a row, OTOH, an "industrial strength" Map implementation might cache the last entry returned.
To avoid it in map.put(key, map.getOrDefault(key, 0) + 1); use a modifiable Number like java.util.concurrent.atomic.AtomicInteger.
Or map.merge(key, 1, Integer::sum).

Not using rank(x)/OrderStatisticTree.indexOf(x) and only index(0)/tree.get(tree.size() - 1), you don't need an order statistic tree in computeArrayWindowMaxima(), the NavigableMultiSet (Bag) the JRE doesn't quite provide should do.
Creating a decorator turning a java.util.Map<T, tally> into a "Bag" - ordered if the map passed into the constructor is - was reusable and improved readability&robustness of "Bag handling" as in computeArrayWindowMaxima().

---

Don't repeat printing an array:

/** Prints an array of integers to <code>out</code>. */
void printArray(PrintStream out, int[] values) // ah, Java primitive arrays
{
 out.println(Arrays.toString(values));
}
/** Prints an array of integers to the standard output stream. */
void printArray(int[] values) { printArray(System.out, values); }

Just for the habit, specify the initial capacity:
counterMap = new HashMap<>(windowLength);

---

If pressed for time, I might forego a decent stab at NavigableMultiSet and use

 NavigableSet<Integer> pq = new TreeSet<Integer>() { // encode array value&index
 final int base = array.length;
 /** encodes array value (more significant)&index */
 int encode(int elementIndex) {
 return array[elementIndex] * base + elementIndex;
 }
 // @Override
 public boolean add(Integer elementIndex) {
 return super.add(encode(elementIndex));
 }
 // @Override
 public boolean remove(Integer elementIndex) {
 return super.remove(encode(elementIndex));
 }
 // @Override
 public Integer last() {
 return super.last()/base;
 }
 };

- smells.