Project Nayuki


Sliding window minimum/maximum algorithm

Sliding window maximum example

Introduction

Suppose we have an array A containing n numbers, and want to compute the minimum or maximum of each possible consecutive k elements. Perhaps we want to apply a maximum filter to an image, or examine how many substrings’ maxima meet a certain criterion. The problem comes up in some programming challenge problems.

The naive brute-force approach is to write two nested for-loops, running in Θ(nk) time (Java code):

int[] maxs = new int[A.length - k + 1];
for (int i = 0; i < maxs.length; i++) {
  int temp = A[i];
  for (int j = 1; j < k; j++) {
    if (A[i + j] > temp)  // Can flip inequality to get minimum
      temp = A[i + j];
  }
  maxs[i] = temp;
}

To speed things up, it is also possible to precompute a table of maxima of certain ranges. But that would be slower and more complicated than the algorithm to be described below.

Deque-based algorithm

The best approach uses a deque (double-ended queue) in a clever way, and runs in Θ(n) time using Θ(k) space. The rest of this discussion assumes a maximization problem, but all the ideas are equally applicable to the minimization problem. The key insight is that the deque always maintains a list of candidate maxima in monotonically decreasing order.

Trivial scenarios

Consider this ascending example (Python code):

A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
k = 4
max(A[0 : 4]) -> 3
max(A[1 : 5]) -> 4
(... et cetera ...)

When we work on the array from left to right, ever new element we see is always bigger than all previous elements seen. Furthermore, the new element “expires” later than all previous elements. These two facts combined mean that we can forget about all previous smaller elements as soon as we see a bigger one.

Now consider this descending example (Python code):

A = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
k = 4
max(A[0 : 4]) -> 9
max(A[1 : 5]) -> 8
(... et cetera ...)

When we work on this array from left to right, the new element is smaller than the previous elements. After we process the substring [9, 8, 7, 6], the 9 on the left needs to be removed, and 5 needs to be added to the right.

Reasoning process

Thinking carefully about those two scenarios, we can come up with these rules for the deque:

  1. The deque shall always represent some kind of processing on a particular range of consecutive array elements, e.g. A[i : j] (Python notation).

  2. When we increment the array range’s right endpoint (j) to add a new element, we manipulate the tail of the deque. Suppose the new element’s value is x. Looping while the deque is non-empty and its tail element is less than x, we remove the tail element. This is because x will be removed later than those elements and x is strictly larger, so those other elements will never be a range maximum from now on. Finally, add x to the tail of the deque.

  3. When we increment the array range’s left endpoint (i) to remove a previously added element, we manipulate the head of the deque. Suppose the just-removed element’s value is x. If the deque’s head element equals x, then remove the head element. This is because x is no longer in the array range, so it cannot be in the deque either. Otherwise the deque’s head element must be greater than x, which means the value x was already removed from the deque at some point in the past. The head of the queue cannot possibly be less than x.

The rules above imply the following properties for our deque:

Finally, we can take these rules and properties and state the data structure semi-formally in terms of invariants:

Source code

More info