Maximum of all subarrays of size k

The problem, simply

You get an array and a window size k. Put a window over the first k numbers and write down the biggest one. Slide the window one step right and do it again, until the window reaches the end. Return the list of biggest numbers. There are n - k + 1 of them.

For [1, 3, -1, -3, 5, 3, 6, 7] and k = 3 the answer is [3, 3, 5, 5, 6, 7].

A story to remember it

Picture it

Examples

Way 1: the simple way

For every window, look at all k numbers and keep the biggest.

1. For each start i from 0 to n - k:
2. Scan arr[i] to arr[i + k - 1] and keep the biggest.
3. Write it down.

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] out = new int[n - k + 1];
        for (int i = 0; i + k <= n; i++) {
            int best = nums[i];
            for (int j = i + 1; j < i + k; j++) {
                best = Math.max(best, nums[j]);   // look at every box in the window
            }
            out[i] = best;
        }
        return out;
    }
}

How long it takes: n - k + 1 windows times k numbers each, O(n * k). Extra room: nothing besides the answer, O(1).

Way 2: the clever way

Keep the list of candidates from the story in a line that can be used at both ends, a deque. Store indexes, not values, so you can tell when a candidate leaves the window.

1. For each index i:
   • If the front index is <= i - k, it has left the window. Remove it from the front.
   • While the number at the back is <= nums[i], remove it from the back. It can never win again.
   • Add i at the back.
   • If i >= k - 1, the window is full. The number at the front is the answer for this window.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] out = new int[n - k + 1];
        Deque<Integer> line = new ArrayDeque<>();     // indexes, biggest value at the front
        for (int i = 0; i < n; i++) {
            if (!line.isEmpty() && line.peekFirst() <= i - k) {
                line.pollFirst();                     // left the window
            }
            while (!line.isEmpty() && nums[line.peekLast()] <= nums[i]) {
                line.pollLast();                      // can never win again
            }
            line.offerLast(i);
            if (i >= k - 1) out[i - k + 1] = nums[line.peekFirst()];
        }
        return out;
    }
}

How long it takes: every index joins the line once and leaves at most once, so all the removals together are O(n). Extra room: the line never holds more than k indexes, O(k).

Another way: a max heap with lazy removal

A heap also finds the max fast. Put (value, index) pairs in a max heap. Before reading the top, throw away tops whose index has left the window. Old pairs deeper in the heap are left alone until they float up, which is why it is called lazy.

import java.util.PriorityQueue;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] out = new int[n - k + 1];
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0])); // max heap
        for (int i = 0; i < n; i++) {
            heap.offer(new int[] { nums[i], i });
            while (heap.peek()[1] <= i - k) heap.poll();  // top left the window
            if (i >= k - 1) out[i - k + 1] = heap.peek()[0];
        }
        return out;
    }
}

This is O(n log n) time and up to O(n) room, since stale pairs can pile up. It is easier to come up with, and it still works when you need more than the max, but the deque is the answer interviewers want.

Watch out for

• Check the front against i - k before you read the answer, not after.
• Use <= when popping from the back. With <, equal numbers pile up. It is still correct, but the line grows.
• The answer array has n - k + 1 slots, and the first answer is written when i == k - 1.
• In the heap way, compare with Integer.compare. Writing b[0] - a[0] overflows for very big and very small numbers.

What interviewers ask next

• Minimum of every window? Same deque, but pop from the back while the back is >= the new number.
• Why is it O(n) when there is a loop inside a loop? Each index is removed at most once in the whole run, so the inner loop runs at most n times in total.
• Sum or average of every window? A running sum is enough: add the new number and subtract the one that left.
• Longest subarray where max minus min is at most a limit? Two deques, one for max and one for min, with a window that grows and shrinks.
• Sliding window median? Two heaps with lazy removal, or two sorted multisets.

Remember this

Grown-up words: the gap in the fence is a sliding window, the list of possible tallest kids is a monotonic deque, crossing off from the back keeps it decreasing, and the heap with old entries left inside is a priority queue with lazy deletion.