Find maximum in sliding window in an array

Question

I was doing one question to find maximum number , given an input array and a sliding windows of given length.

Input

nums = [-4,2,-5,1,-1,6]
window_size = 3

Output

result = [2,2,1,6]

The solution uses deque data structure to track the index and store the maximum value. Below is the code for the solution.

class MaxSlidingWindow {
    public static ArrayDeque<Integer> findMaxSlidingWindow(int[] arr, int windowSize) {
        ArrayDeque<Integer> result = new ArrayDeque<>(); // ArrayDeque for storing values
        Deque<Integer> list = new ArrayDeque<Integer>(); // creating a linked list

        if (arr.length > 0) {
            // If window_size is greater than the array size,
            // set the window_size to nums.size()
            if (arr.length < windowSize)
                windowSize = arr.length;
            for (int i = 0; i < windowSize; ++i) {
                // Removing last smallest element index
                while (!list.isEmpty() && arr[i] >= arr[list.peekLast()]) {
                    list.removeLast();
                }

                // Adding newly picked element index
                list.addLast(i);
            }

            for (int i = windowSize; i < arr.length; ++i) {
                result.add(arr[list.peek()]);

                // Removing all the elements indexes which are not in the current window
                while ((!list.isEmpty()) && list.peek() <= i - windowSize)
                    list.removeFirst();

                // Removing the smaller elements indexes which are not required
                while ((!list.isEmpty()) && arr[i] >= arr[list.peekLast()])
                    list.removeLast();

                // Adding newly picked element index
                list.addLast(i);
            }

            // Adding the max number of the current window in the result
            result.add(arr[list.peek()]);
            return result; // returning result
        } else
            return result;
    }

Now I couldn't get the condition mentioned in the while loop that says "removing all the elements indexes which are not in the current window" while ((!list.isEmpty()) && list.peek() <= i - windowSize) . How could have author approached this condition list.peek() <= i - windowSize to remove all the elements which are not in current window.

If some one can give me a break down that how we can reach to this logic or is there any other intuitive condition that does the same job . It would be better if I can get some easy explanation of the above condition used by the author.

Secondly the author has used ++i in the for loops . Is there a specific reason to choose the pre-increment for this question.

Answer 1

What you are doing here is to build an increasing mono queue based on the sliding window.

Since the sliding window moves forward, you need to remove "possible" indices that are out of bound of the sliding window. That's what this line does:

// Removing all the elements indexes which are not in the current window
while ((!list.isEmpty()) && list.peek() <= i - windowSize)
    list.removeFirst();

i is the index where the front of your sliding window lies and i - windowsize is the back of the window. You check wheather the head of the deque contains an index that is smaller and remove it, since it lies outside of the sliding window.

As for your second question, @JC677 explained it quite thoroughly in their comments. It doesn't make a functional difference here. It's probably the author's style.