Sliding Window Maximum

The problem

Given a list of integers nums and a number k, picture a window that shows k neighboring numbers. It starts at the left end of the list and moves one position to the right at a time until it reaches the right end. Return a list with the largest number in the window at each position, from left to right. Aim for a method that takes O(n) time.

What to write

function solve(nums: number[], k: number): number[]

Input
nums = [1,3,-1,-3,5,3,6,7]
k = 3

Output
[3,3,5,5,6,7]

Input
nums = [1]
k = 1

Output
[1]

Constraints

1–10,000 integers; 1 ≤ k ≤ nums.length.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There can be 10,000 numbers, and k can be anything up to that. Finding each window's largest number from scratch costs about 25 million comparisons when k is 5,000. Two neighboring windows share all but one of their numbers, so most of that work is repeated.

2. Hint 2: Ask a smaller question

   A window holds 3 and then -1. While that 3 is inside the window, can the -1 be the largest? And after the 3 has left? Now a 5 arrives. Can the 3 or the -1 ever be the largest again?

3. Hint 3: Name the pattern

   A number can be forgotten once a number at least as large arrives after it, because the newer one stays in the window longer. The candidates that remain get smaller from oldest to newest; new ones join at the back, old ones leave at the front. A queue whose values only go one way is a monotonic queue. Read the lesson on monotonic queue.

4. Hint 4: State the invariant

   The queue holds positions that are inside the current window, oldest first, and their values get strictly smaller from front to back. So the value at the front is the largest in the window.

5. Hint 5: Sketch the pseudocode

   Keep a queue of positions. For each position i: remove the front if it is i - k or less. Remove from the back while the value there is not larger than the value at i. Add i at the back. If i ≥ k - 1, append the front's value to the answer. Return the answer.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Keep a deque of indices with decreasing values. Remove expired indices from the front and dominated values from the back; the front is the window maximum.

The slow way

For each window, scan its k numbers and take the largest. It is correct, but neighboring windows share all but one number and the scan starts again every time. With 10,000 numbers and k = 5,000 that is about 25 million comparisons.

The insight

When a new number arrives, every earlier number that is not larger can be thrown away. The new one is at least as big and stays in the window longer. The numbers that survive are in falling order, so the largest is always the oldest survivor.

Step by step

1. Keep a queue of positions whose values fall from front to back. A queue is a line: new positions join at the back and old ones leave at the front. This one also drops positions from the back, which makes it a double-ended queue, a deque for short.
2. Drop the front position once it has slid out of the window. The window that ends at position i starts at i - k + 1, so position i - k is outside it. Only the front can be that old, because the queue is in order of arrival.
3. Drop from the back every value that is not larger than the new one. Such a number arrived earlier and is no bigger, so it leaves the window first and is never needed as the largest while the new one is there.
4. Add the new position at the back. The position goes in, not the value, because a position also tells you when the number has left the window. Everything still in the queue is larger than the new number, so the falling order holds.
5. Once the first window is full, report the value at the front. Values fall from front to back, so the front is the largest in the window. The first k - 1 positions do not complete a window, so nothing is reported for them.
6. Return the maximum collected for every window. One value was reported for each position from k - 1 to the end. That is one per window, in order from left to right.

The same numbered steps are the comments in each solution.

function solve(nums, k) {
  // 1. Keep a queue of positions whose values fall from front to back
  const q = [],
    out = [];
  // Removing an array's first entry moves all the others,
  // so h marks the front of the queue instead.
  let h = 0;
  for (let i = 0; i < nums.length; i++) {
    // 2. Drop the front position once it has slid out of the window
    while (h < q.length && q[h] <= i - k) h++;
    // 3. Drop from the back every value that is not larger than the new one
    while (q.length > h && nums[q[q.length - 1]] <= nums[i]) q.pop();
    // 4. Add the new position at the back
    q.push(i);
    // 5. Once the first window is full, report the value at the front
    if (i >= k - 1) out.push(nums[q[h]]);
  }
  // 6. Return the maximum collected for every window
  return out;
}

function solve(nums: number[], k: number): number[] {
  // 1. Keep a queue of positions whose values fall from front to back
  const q = [],
    out = [];
  // Removing an array's first entry moves all the others,
  // so h marks the front of the queue instead.
  let h = 0;
  for (let i = 0; i < nums.length; i++) {
    // 2. Drop the front position once it has slid out of the window
    while (h < q.length && q[h] <= i - k) h++;
    // 3. Drop from the back every value that is not larger than the new one
    while (q.length > h && nums[q[q.length - 1]] <= nums[i]) q.pop()!;
    // 4. Add the new position at the back
    q.push(i);
    // 5. Once the first window is full, report the value at the front
    if (i >= k - 1) out.push(nums[q[h]]);
  }
  // 6. Return the maximum collected for every window
  return out;
}

from collections import deque


def solve(nums, k):
    # 1. Keep a queue of positions whose values fall from front to back
    queue = deque()
    out = []
    for i, num in enumerate(nums):
        # 2. Drop the front position once it has slid out of the window
        while queue and queue[0] <= i - k:
            queue.popleft()
        # 3. Drop from the back every value that is not larger than the new one
        while queue and nums[queue[-1]] <= num:
            queue.pop()
        # 4. Add the new position at the back
        queue.append(i)
        # 5. Once the first window is full, report the value at the front
        if i >= k - 1:
            out.append(nums[queue[0]])
    # 6. Return the maximum collected for every window
    return out

Example 1, traced

Input
nums = [1,3,-1,-3,5,3,6,7]
k = 3

Output
[3,3,5,5,6,7]

Why it works

The queue always holds positions inside the window, in order of arrival, with values that get strictly smaller. A number is removed only when it has left the window or when a newer number at least as large has arrived. So the window's largest value is always still in the queue, and since the values fall from front to back, it is at the front.

Time and space

Time O(n), extra space O(n) in this array-backed deque. Each position is added once and removed at most once, so the two inner loops run at most n times in all: O(n). The JavaScript queue is a plain array that only marks its front, so positions dropped there stay in memory and it can reach n entries: O(n) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Clear the back with a loop, not a single test. One arriving number can beat several waiting ones: in example 1 the 5 removes both -3 and -1. A single test gives 3, 3, -1, 5, 5, 7.
• The front leaves when its position is i - k or less. Testing for less than i - k keeps it one step too long: [3, -3] with k = 1 gives [3, 3], not [3, -3].
• Report nothing until k numbers have been read. Reporting from the first position gives example 1 eight values instead of six.

Pattern

Monotonic queue. Builds on Permutation In String.

Keep going