Solution: A Running Maximum

Recall the Moving Average practice problem from the queue chapter:

• We wanted to find the average of the last k values in a stream of numbers.
• We solved it by storing the last k values in a queue and keeping a running sum of those values.
• On every call to add, we add the new value to the queue and to the sum, and if the queue has more than k values, we remove the oldest value from the queue and subtract it from the sum.

The moving average gets its $O(1)$ time from updating a running sum. The obvious way to copy that here is a running maximum: a single variable called max, updated as the window slides:

• Find the maximum of the first window and store it in max.
• If the entering value is larger than max, it becomes the new max; otherwise we keep the previous max.

Here is that idea in code:

public static int[] slidingMaximum(int[] values, int k) {
  int[] answer = new int[values.length - k + 1];

  // find the maximum of the first window
  int max = values[0];
  for (int i = 1; i < k; i++) {
    if (values[i] > max) {
      max = values[i];
    }
  }
  answer[0] = max;

  // slide the window one position at a time (past the first window)
  for (int start = 1; start <= values.length - k; start++) {
    int entering = values[start + k - 1];
    if (entering > max) {
      max = entering;
    }
    answer[start] = max;
  }

  return answer;
}

Finding the maximum of the first window takes about k comparisons. After that, each slide does a single comparison: the entering value against max. So the whole algorithm is $O(n)$, no matter how large the window is. That is faster than brute force, which does about k comparisons per window. Now we have to check whether it still gives the right answer.

Start with an easy case:

values = [1, 3, -1, -3], k = 3

The first window is [1, 3, -1], so max is 3. The next window is [3, -1, -3]. The entering value is -3, which is not larger than 3, so keeping max = 3 is correct.

Now try another example:

values = [9, 1, 2, 3], k = 3

The first window is [9, 1, 2], so max is 9. When the window slides, 9 leaves and 3 enters:

[9, 1, 2], 3      max is 9
 9, [1, 2, 3]     max should be 3

Our running max stays at 9. The entering value 3 is not larger than 9, so the update rule never changes it. The problem is that the maximum left the window.

When a value leaves the moving average’s window, the running sum is easy to update: subtract that value. A maximum cannot be updated that way. Once the largest value leaves, we have no record of what the next largest is.

Can we fix the running maximum? There is only one way to fix it and still keep a single max variable: when the value leaving the window is the maximum, rescan the window to find the new maximum. When the leaving value is not the maximum, we keep max as before.

This strategy will give the correct answer, so it is a valid solution. But it is no longer $O(n)$, because of the rescans. Those rescans are exactly what the brute force solution does. We have only delayed them until the maximum leaves. On some inputs the maximum rarely leaves, so the rescans are rare and the method stays close to $O(n)$. But on the worst-case inputs, the maximum leaves on every slide:

values = [9, 8, 7, 6, 5, 4], k = 3

When 9 leaves, scan [8, 7, 6]. When 8 leaves, scan [7, 6, 5]. When 7 leaves, scan [6, 5, 4]. The maximum leaves on every slide, so we rescan on every slide. That is the same $O(nk)$ cost as brute force, with a solution that is more complicated than the brute force approach.

We do not just need the current maximum. We need a way to recover the next maximum when the current one leaves.