Sliding Window Maximum

HARD✓ CHIP-TIMEDLC #239 — FULL STATEMENT ↗

The drill: A fixed-width window slides along an array one step at a time; report the largest value it holds at every stop. Rescanning k elements per stop throws nearly all of its work away — the winning tool is a queue that drops anyone who can never lead again.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of integers and a window width k arrive together. Picture a window of that width sliding across the array one position at a time, from the very start until it falls off the end.

At each stop along that slide, the drill wants the largest value currently inside the window. The result is one number per stop, in the same order the window visits them.

The window always holds exactly k elements while it's sliding, and k never exceeds the array's own length, so every stop produces a valid maximum.

EX 01

nums = [3, 1, 4, 1, 5] · k = 2

→ [3, 4, 4, 5]

PAIRWISE DUELS

EX 02

nums = [7, 2, 5, 1, 8, 3] · k = 3

→ [7, 5, 8, 8]

LEADER EXPIRES, RUNNER-UP TAKES OVER

EX 03

nums = [9, -4, 6] · k = 1

→ [9, -4, 6]

K = 1 — EVERY ELEMENT IS ITS OWN WINDOW

array length can reach into the tens of thousands
window width k is at least 1 and never exceeds array length
one maximum reported per window position, left to right
values may repeat and can be negative

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Between one stop and the next, only two things change: one value enters on the right, one expires on the left. What knowledge from the last window deserves to survive the slide?

HINT 2 THE STRUCTURE

A value with a newer, bigger-or-equal neighbour to its right can never be a window maximum again — it is dominated for the rest of its life. Keep only the undominated, and notice they form a decreasing lineup.

HINT 3 ONE STEP FROM THE ANSWER

Hold indices in a deque, values decreasing front to back. On arrival, pop the back while it is ≤ the newcomer, then push; pop the front once its index leaves the window. The front is the answer at every stop.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE UNDOMINATED DEQUEPATTERN · MONOTONIC DEQUEnums = [3, 1, 4, 1, 5] · k = 2

DEQUE — INDEX:VALUE, FRONT→BACK

— empty —

STEP 1

k=2. Keep a deque of indices with values decreasing front to back — the front is always the current window's max.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/sliding-window-maximum.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = collections.deque()  # indices; their values run decreasing
        out = []
        for i, v in enumerate(nums):
            while dq and nums[dq[-1]] <= v:  # dominated — never a max again
                dq.pop()
            dq.append(i)
            if dq[0] <= i - k:  # front slid out of the window
                dq.popleft()
            if i >= k - 1:
                out.append(nums[dq[0]])
        return out

TIME O(N)SPACE O(K)PYTHON · RACE PACE · 13 LN

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # rescan all k elements at every stop
        return [max(nums[i:i + k]) for i in range(len(nums) - k + 1)]

TIME O(N·K)SPACE O(1)PYTHON · TRAINING PACE · 4 LN

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] out = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>(); // indices; their values run decreasing
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast(); // dominated — never a max again
            }
            dq.addLast(i);
            if (dq.peekFirst() <= i - k) {
                dq.pollFirst(); // front slid out of the window
            }
            if (i >= k - 1) {
                out[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return out;
    }
}

TIME O(N)SPACE O(K)JAVA · RACE PACE · 20 LN

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]; // rescan all k elements at every stop
            for (int j = i + 1; j < i + k; j++) {
                best = Math.max(best, nums[j]);
            }
            out[i] = best;
        }
        return out;
    }
}

TIME O(N·K)SPACE O(1)JAVA · TRAINING PACE · 14 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED