Sliding window min/max - Dynamic Programming - Algorithms and Problem SolvingAlgorithms and Problem Solving

Sliding window min/max - Dynamic Programming - Algorithms and Problem SolvingAlgorithms and Problem Solving

Given an array of integer A[] and the size of sliding window w. Assume that the window of size w starting from left keeps sliding by moving the window one element to right each time. Find the stream of sliding minimums in optimal way. A sliding minimum is the minimum element of current window.

Let's start with an example for our convenience.

             sliding window                Min         Max              ---------------               -----       -----              [1  2  -1] -3  4  2  5  3       -1          2               1 [2  -1  -3] 4  2  5  3       -3          2               1  2 [-1  -3  4] 2  6  3       -3          4               1  2  -1 [-3  4  2] 5  3       -3          4               1  2  -1  -3 [4  2  5] 3        2          5               1  2  -1  -3  4 [2  5  3]       2          5  

First, let us concentrate on finding sliding min. An O(n*w) bruteforce solution would be to do go through each of the element of the array and find minimum of w elements from the current position to the right. There could be another solution using heap for maintaning the min of sliding window. This is of O(nlgw) time and O(lgw) space complexity. But we can do far better in O(n) using a DP approach.

Observe that element at position i can be shared across sliding windows starting at most w positions to left of i including i. So,  the sliding minimum at a position is the minimum of  a block of w elements from current position to the right and the minimum of a block of w elements from current element to the left.

So, we can  divide the array into [n/w] blocks. Then we can find min in left while traversing from left to right of the current window. But what about min in right? the trick is that we can traverse backwards to get the right min at a position. Also note that: windows separated by elements >=w will have no overlapping. So, left min/right min should be reset at the boundary of each block of w elements in the direction of traversal.

For Example: A = [2,1,3,4,6,3,8,9,10,12,56],  w=4

1. partition the array in blocks of size w=4. The last block may have less then w.
   2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|
2. Traverse the list from start to end and calculate min_so_far. Reset min to 0 after each block (of w elements).
   left_min[] = 2, 1, 1, 1 | 6, 3, 3, 3 | 10, 10, 10
3. Similarly calculate min_in_future by traversing from end to start.
   right_min[] = 1, 1, 3, 4 | 3, 3, 8, 9 | 10, 12, 56
4. now, min at each position i in current window, sliding_min(i) = min {right_min[i], left_min[i+w-1]}
   sliding_min = 1, 1, 3, 3, 3, 3, 8, ….

//base cases  left_min[0] = A[0]  right_min[n - 1] = A[n - 1]    //DP  left_min[i]  = (i % w == 0) ? A[i] : min{left_min[i - 1], A[i]}, for  i = [1..(n-1)]  right_min[j] = (j % w == 0) ? A[j] : min(right_min[j + 1], A[j]), for j = [(n-1).. 0]    //Optimization  sliding_min[i] = min{right_min[i], left_min[i + w - 1]}, for i = [0..(in.length - w + 1)]  

Read full article from Sliding window min/max - Dynamic Programming - Algorithms and Problem SolvingAlgorithms and Problem Solving