Algorithm Prototype: Sliding Window

What is Sliding Window?

Sliding window is more like a techniques than algorithm.

Basically we need an array, and two pointer: left & right to mark the boundary of window.

Also we have some kind of constraint on this window, a typical situation is,

moving forward right pointer until the constraint is not satisfied, then move left pointer to make the constraint satisfied again.

Prototype

In this article, I will use this prototype: how to maintain the max value inside a sliding window

1. maintain a queue, to store the position of value
2. we also need to ensure the queue’s property, its content is sorted. biggest element is on queue header, smallest element is on tail
3. as we expand the window:
   1. if the new element is smaller than queue tail, then just push it into queue
   2. if the new element is bigger than queue tail, then pop out the tail element until it’s bigger than the new element

logic should looks like

LinkedList<Integer> queue = new LinkedList<>();

// ... some logic
int newElement = arr[right];
while(!queue.isEmpty() && arr[queue.peekLast()] <= newElement) {
    queue.pollLast();
}
queue.offer(right);

// ... some logic

so essentially, the queue stores the priority of the element which can be the biggest value at current window

Challenge 1

assume the window size is fixed as w, 

given an array, return the max value of each possible window

eg, given [4,3,5,4,3,3,6,7], w = 3 
the result is [5,5,5,4,6,7]

public int[] solution(int[] arr, int w) {
    ArrayList<Integer> res = new ArrayList<>();
    LinkedList<Integer> max = new LinkedList<>();
    
    int l = 0, r = 0;
    while (r <= arr.length) {
        if (r - l < w) {
            while(!max.isEmpty() && arr[max.peekLast()] <= arr[r]) {
                max.pollLast();
            }
            max.offer(r++);
        } else {
            res.add(arr[max.peekFirst()]);
            if (l == max.peekFirst()) {
                max.pollFirst();
            }
            l++;
        }
    }
}

Challenge 2

Given an arr, and an integer: num
the sub array can be qualified if its `max - min <= num`

return the count of qualified sub array.

If count all qualified sub array, it would be N^3 time complexity. so actually this problem can be transferred to :

How many sub array starting from each element.

public int countQualifiedSubArray(int[] arr, int num) {
    int left = 0, right = 0;
    // [left, right)
    
    // queue contains the max value
    LinkedList<Integer> maxQueue = new LinkedList<>();
    // queue contains the min value
    LinkedList<Integer> minQueue = new LinkedList<>();
    
    int res = 0;
    // 1. involve right element into queues
    // 2. check if the condition is qualified
    // 3. if condition is qualified, move right pointer to next position
    // 4. if condition is not qualified, then settle current left result, move forward left pointer
    // 5. when right pointer reach the end, sum up all the rest sub array cause all of them are qualified
    while(right < arr.length) {
        
        // update right value into maxQueue & minQueue
        while(!maxQueue.isEmpty() && arr[maxQueue.peekLast()] <= arr[right]) {
            maxQueue.pollLast();
        }
        maxQueue.offer(right);
        
        while(!minQueue.isEmpty() && arr[minQueue.peekLast()] >= arr[right]) {
            minQueue.pollLast();
        }
        minQueue.offer(right);
        
        if(arr[maxQueue.peekFirst()] - arr[minQueue.peekFirst()] > num) {
            // settle down current result
            res += (right - left);
            
            if (maxQueue.peekFirst() == left) {
                maxQueue.pollFirst();
            }
            if (minQueue.peekFirst() == left) {
                minQueue.pollFirst();
            }
            left++;
        } else {
            right++;
        }
        
    }
    
    // when right pointer reach arr end, means current [left, right) is qualified array, then all sub array are qualified array as well
    while(left < arr.length) {
        res += (right - left++);
    }
    
    return res;
}

Retro

• When encountering the problem like counting the qualified sub array, instead of traverse all sub arrays, we can transform the problem to, starting from each element, how many sub arrays are qualified
• one signal indicating to use sliding window is the “monotonicity” and the array range, for example, if one array’s (max - min <= num), then all of its sub array are qualified as well.