Problem Statement

Give an array and a sliding window size that moves from left to right, find the maximum value in the sliding window.

Approach 1:

A straight forward approach is to cacluate the maximum value of each of the sliding window, if the array size is \(n\), and sliding window is \(k\), then time complexity is \(O(kn)\).

Apprach 2:

Because the sliding window moves only one position each time, we could reuse the information from the last step. It means the sliding windows only add and remove ONE element each time, all the other elements are still the same. We can use a container that could calculate the maximum value automatically to keep the elements in the window, and also could remove and add element.

Priority Queue is one option, it could calculate maximum value at \(O(logn)\), add element at \(O(logn)\), but it need \(O(n)\) to remove a specific element. That means the overall time complexity is still \(O(kn)\).

The other option is Binary Search Tree, which perform all the above operation with \(O(logn)\). In Java, TreeMap could be use, because repeat element could be in the window. This approach takes \(O(nLogk)\).

    private int[] heapMethod(int[] nums, int k) {
        
        TreeMap<Integer, Integer> maxHeap = new TreeMap<>((x,y)-> -1*Integer.compare(x,y));
        
        int[] res = new int[nums.length - k + 1];
        
        for (int i = 0; i <= nums.length; i++) {
            if (i < k) {
               maxHeap.put(nums[i], maxHeap.getOrDefault(nums[i], 0)+1); 
            } else {
                res[i - k] = maxHeap.firstEntry().getKey();
                if (i == nums.length) break;
                maxHeap.put(nums[i - k],maxHeap.get(nums[i - k])-1);
                
                if (maxHeap.get(nums[i-k]) <= 0) 
                    maxHeap.remove(nums[i-k]);
                
                maxHeap.put(nums[i],maxHeap.getOrDefault(nums[i],0)+1);
            }
        }
        return res;
    }

Approach 3

The previous appraches basically calcuate the maximum value in every sliding window, with either \(O(n)\) or \(O(logn)\). However, we could save time if we disregard the unuseful elements. For example, the window below [-1, -3, 5], we already know the maximum is 5. When we move the window to next one, we could remove -1 and -3, because they couldn’t be maximum value of any window after this point.

This step could be done when we see 5 the first time. That is, we could remove values in the window that is less than the current value. So we have a window like below for the example above:

1: [1] see 1, put it in
3: [3] see 3, remove 1
-1: [3, -1] see -1, put it in because -1 could be a maximum of windows after
-3: [3, -1, -3] see -3, put it in with the same reason
5: [5] see 5, remove all and put 5 in, because all previous elements couldn’t be maximum value of any window after
3: [5, 3] see 3, put it in
6: [6] see 6, remove all previous
7: [7] see 7, remove all previous \

This way, the maximum value of every windows is always the head element. Since we have to operate in two directions of the container, we could use a deque.

    private int[] dqMethod(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> dq = new LinkedList<>();
        
        for (int i = 0; i < nums.length; i++) {
            
            // if deque's first element is not in the window, remove it.
            if (i >=k && nums[i-k] == dq.peekFirst()) dq.pollFirst();    
            
            //remove any element that's less than the current one. Note it should compare and remove from backside, because the first element is the maximum element.
            while(!dq.isEmpty() && dq.peekLast() < nums[i])
                dq.pollLast();
            // push current element to end
            dq.offerLast(nums[i]);           
            if (i >= k-1) res[i-k+1] = dq.peekFirst();  
        }

        return res;
    }

Exmaples

LeetCode - 239 1696

LeetCode 239 could use the method above directly. LeetCode 1696 need to use this trick to pass all the test case.

LeetCode - 1499

Using brutal force, we could centainly solve it by \(O(n^2)\). By observing the equation and the constraint, this is actually a maximum sum of sliding window problem. The equation could be:

Basically, we need to store the previous points with \(max(y_i-x_i)\) that within \(k\) distance from current point \(j\). Therefore, we only need to maintain a window of maximum size \(k\), and scan from left to right to ensure \(x_j > x_i\). When we see a point, firstly, we need to throw all points that not within \(k\). When we add the current point to the queue, we need to throw all points that gives less \(y-x\) than the current point, because they are old point than the current one. Thus, the first points in the queue is the points that gives maximum \(y_i-x_i\).

    public int findMaxValueOfEquation(int[][] points, int k) {
        
        Deque<int[]> dq = new LinkedList<>();
        
        int max = Integer.MIN_VALUE;
        for (int j = 0; j < points.length; j++) {
            
            // throw all points outside of k distance
            while(!dq.isEmpty() && dq.peekLast()[0] + k < points[j][0]) {
                dq.pollLast();
            }
            
            // the last point in the window gives the max value for current point
            if(!dq.isEmpty()) {
                max = Math.max(dq.peekLast()[1]-dq.peekLast()[0]+points[j][0]+points[j][1], max);
            }
            
            // throw all points that is less than yj-xj from the front of the queue
            while(!dq.isEmpty() && dq.peekFirst()[1]-dq.peekFirst()[0] < points[j][1] - points[j][0]) {
                dq.pollFirst();
            }
            dq.offerFirst(points[j]);
        }
        
        return max;
    }

Leetcode - 862

This problem removes the contraints of positive number, i.e., the number could be negtive. Simple sliding window wouldn’t give corrent answer, because the prefix sum is not monotonic increasing. Suppose prefix sum is calculated as \(P_i\). Then this problem is basically an optimizing problem as:

Obviously, an \(O(n^2)\) is able to solve it. But if we observe it carefully, for each of \(j\), we need to find maximum previous index \(i\) so that \(P_j >= P_i + k\). Another observation is for each of previous \(P_i\), if \(P_j < P_i\), then \(P_i\) doesnot have any oppurtunity to form a minimum subarray, because any later index would use \(P_j\) instead of \(P_i\). We can therefore use a deque to store the previous prefix sum and, based on the above observations to remove elements accordingly.

    public int shortestSubarray(int[] nums, int k) {
      
        int n = nums.length;
        long[] preSum = new long[n+1];
        for (int i = 1; i < n+1; i++){
            preSum[i] = preSum[i-1] + (long)nums[i-1];
        }
        
        int i = 0, j = 0;
        int ans = n+1;
        
        Deque<Integer> dq = new LinkedList<>();
        
        while (j < n+1) {
        
            // if previous sum is more than current sum, then current index j is a better candidate for later use
            // because we need to minimum index difference.
            while(!dq.isEmpty() && preSum[dq.peekLast()] > preSum[j]) {
                dq.removeLast();
            }
            // if previous sum preSum[i] + k <= preSum[j], then we can calculate the index and throught it away,
            // because preSum[i] is best been used for current index, not for later
            
            while(!dq.isEmpty() && preSum[dq.peekFirst()] + k <= preSum[j]) {
                ans = Math.min(ans, j - dq.removeFirst());
            }
            
            dq.offerLast(j++);
        }
        
        if (ans == n+1) return -1;
        return ans;
    }