[Java] Find maximum in all subarrays of length K

Given an array of integers and a window size K, find the maximum element for all subarrays in each window.

Example:

1234 and K = 2

(1,2) - 2

(2,3) - 3

(3,4) - 4

An interesting solution that comes up is to use a max heap of maximum size K to track the maximum element within a window of size K over the array.

When we slide the window, we delete from the heap the element that was at the start and add the element that is at the end. This costs O(logK) for both delete and insert. Doing this operation for each element in the input array yields O(N logK) time and O(K) space complexity. For example:

 public static void maxOfK(int[] numbers, int k){  
   PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((e1,e2) -> -e1.compareTo(e2));  
   int i = 0;  
   for(int j = 0; j < numbers.length; j++){  
     maxHeap.add(numbers[j]);  
     if(maxHeap.size() == k){  
       System.out.println(maxHeap.peek());  
       maxHeap.remove(numbers[i]);  
       i++;  
     }  
   }  
 }  

However a challenge is to do this in O(N) time and O(K) space only.

We use a doubled ended queue (doubly linked list) and enqueue the first K elements. Side note, in Java the Queue interface does NOT offer methods to work at both ends, therefore we need to use a specific ArrayDequeue or LinkedList instead.

We keep a pointer to the beginning of the window and start our walk from position K.
Each new element that comes can be:

(1) biggest of all other elements in the queue, this means that until the window cuts him out he will be the maximum

(2) bigger than some other elements in the queue, this means that as soon as the window cuts out the current maximum he MIGHT be the new maximum, for sure not the other currently smaller elements

(3) smallest of all other elements in the queue, this means that as soon as the window cuts out the current maximum he MIGHT be the new maximum, unless bigger elements come after us that would end up in the same window as us

Simply put, at each step we:

(1) verify if the window has cut out the current maximum and if so, remove it from front of the list

(2) add the new element at the back of the list. While adding, we try to push ourselves as far towards the front as possible, removing all elements smaller than us while doing so. This is because within this window size, they will never be the maximum and since we came after them, even when the window moves forward they have no chance of being the maximum.

Example:

4321 window size 2

queue is 4,3 maximum is 4
window slides and cuts off 4 and includes 2 - queue is 3,2 maximum is 3
window slides and cuts off 3 and includes 1 - queue is 2,1 and maximum is 2

1234 window size 2

queue is 1,2 maximum is 2
window slides and cuts off 1 and includes 3 - queue is 2,3 but in this window and until the window cuts 3 off (unless a bigger element appears) 3 will be the maximum, we push it to the front and queue is 3 only
window slides and cuts off 2 and includes 4 - queue is 3,4 as before we push 4 to the front, queue is 4 only

You can check my implementation of findMaximumForEachSubarrayOfLengthK on my Gist along with some tests in FindMaximumForEachSubarrayOfLengthKJTests.