Sliding window min/max – Dynamic Programming

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)]

This is only O(n) time solution with O(n) space.

public static int[] slidingWindowMin(final int[] in, final int w) {
    final int[] min_left = new int[in.length];
    final int[] min_right = new int[in.length];

    min_left[0] = in[0];
    min_right[in.length - 1] = in[in.length - 1];

    for (int i = 1; i < in.length; i++) {
        min_left[i] = (i % w == 0) ? in[i] : Math.min(min_left[i - 1], in[i]);

        final int j = in.length - i - 1;
        min_right[j] = (j % w == 0) ? in[j] : Math.min(min_right[j + 1], in[j]);
    }

    final int[] sliding_min = new int[in.length - w + 1];
    for (int i = 0, j = 0; i + w <= in.length; i++) {
        sliding_min[j++] = Math.min(min_right[i], min_left[i + w - 1]);
    }

    return sliding_min;
}

 

Similarly for sliding window max for each position i, we will take the max of left_max(i+w-1) and right_max(i) .

sliding-max(i) = max{right_max(i), left_max(i+w-1)}

public static int[] slidingWindowMax(final int[] in, final int w) {
    final int[] max_left = new int[in.length];
    final int[] max_right = new int[in.length];

    max_left[0] = in[0];
    max_right[in.length - 1] = in[in.length - 1];

    for (int i = 1; i < in.length; i++) {
        max_left[i] = (i % w == 0) ? in[i] : Math.max(max_left[i - 1], in[i]);

        final int j = in.length - i - 1;
        max_right[j] = (j % w == 0) ? in[j] : Math.max(max_right[j + 1], in[j]);
    }

    final int[] sliding_max = new int[in.length - w + 1];
    for (int i = 0, j = 0; i + w <= in.length; i++) {
        sliding_max[j++] = Math.max(max_right[i], max_left[i + w - 1]);
    }

    return sliding_max;
}

21 thoughts on “Sliding window min/max – Dynamic Programming

  1. This is an awesome answer.
    Is there a video for this anywhere showing how it is computed? That would be great.

    I’m wondering if this can be used to find the top k numbers in a sliding window of w

  2. When you traverse from end to start for right_min, shouldn’t it be:
    min_right[j] = ((i + 1) % w == 0) ? in[j] : Math.min(in[j], min_right[j + 1]);
    so that the blocks are exactly what you mentioned in the post.

    When I tried
    min_right[j] = (j % w == 0) ? in[j] : Math.min(min_right[j + 1], in[j]);
    the result was
    min_right = {2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56}

    When I tried
    min_right[j] = (j % w == 0) ? in[j] : Math.min(min_right[j + 1], in[j]);
    the result was
    min_right = {1, 1, 3, 4, 3, 3, 8, 9, 10, 12, 56}

    Either way, both the approaches yield the same result for sliding_min in the end.

    • yes, you can implement that traverse any other way you want but the norm here that you make sure you know the boundary of each block so that you are properly resetting the min to zero at the boundary. Otherwise, computing min within a block is no big deal.

    • in this case :
      in[] => 1 -2 5 6 0 9 8 -1 2 0 and w = 3.

      your expression:
      min_right[j] = ((i + 1) % w == 0) ? in[j] : Math.min(in[j], min_right[j + 1]);
      won’t work because there should be a boundary at in[8] and according to this expression it is producing it on in[7];

      Correction:
      either you do this:
      int offset = w – in.length%w;
      min_right[j] = ((i + offset) % w == 0) ? in[j] : Math.min(min_right[j + 1], in[j]);

      or this:

      min_right[j] = (j % w == w – 1) ? in[j] : Math.min(min_right[j + 1], in[j]);

      • The code is right as it is. For your case,

        in[] => 1 -2 5 6 0 9 8 -1 2 0 and w = 3.

        the code generates output :
        sliding max : [5, 6, 6, 9, 9, 9, 8, 2]
        sliding min : [-2, -2, 0, 0, 0, -1, -1, -1]

  3. Awesome concept.. Just not intuitive, how did you get this concept intuitivly or if we want, how can we think in this way ?

    • The idea is to find the maximum of the left part and the maximum of the right part, and then obtain the maxima by comparing the two maximums.

      The keen observation is that all the left maximums can be found by a right-to-left transverse, while all the right maximums can be found by a left-to-right transverse.

      Here is a short explanation to above algorithm.

      Suppose the numbers are | a , b , c ,d | e, f , g , h | ..
      After storing the max value for each window both in left and right direction, we have the arrays
      left : |a, b, b , d| e , e, e , h|..
      right: |d,d,d,d| h, h, h h | ..

      Finally in the last loop, when you’re in the first window, the maxValue is calculated with following formula
      max(i) = Math.max( max_right[i], max_left[i+w-1] ) in this we test the maximum on both end of the window, i.e, left direction and right direction.
      and then we move to next window find their maximum.

      I hope it makes the algorithm clearer.

  4. Thanks all for all useful comments. It’s been a while since I was active in this blog. But I’ll try my best to keep responding and solve more questions.

Comments are closed.