Sliding Window Maximum — Problem Statement & Solution Guide

Sliding WindowHardSliding Window / Monotonic Deque

TimeO(n)

SpaceO(k)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Sliding Window and solve the Sliding Window Maximum problem optimally.

TopicSliding Window

PatternSliding Window / Monotonic Deque

TimeO(n)

SpaceO(k)

Problem Description

Given an integer array nums and a positive integer k, slide a window of length k from the leftmost element to the rightmost element of the array. For each window position, output the greatest value contained in that window. The windows are contiguous sub‑arrays of size exactly k; the first window comprises nums[0] through nums[k‑1], the second window comprises nums[1] through nums[k], and so on until the window ends at nums[nums.length‑1]. Return the sequence of maximums in the order the windows appear.

DSA Pattern Breakdown

"Sliding Window Maximum"

hard

WHY DOES IT MATTER?

The sliding window maximum pattern teaches candidates how to transform a seemingly quadratic problem into linear time by exploiting the order of arrival and departure of elements. Mastery of this pattern signals an ability to design streaming algorithms that operate under strict latency constraints, a skill highly prized in real‑time analytics, monitoring, and high‑frequency trading systems.

OPTIMIZATION CHALLENGE

The key insight is maintaining a decreasing deque so that each element is inserted and removed at most once. This amortized constant‑time guarantee eliminates redundant comparisons and ensures O(n) total work, the crux of the optimization over the naïve O(n·k) scan.

REAL-WORLD CONNECTION

Think of a network router that must constantly report the highest packet size seen in the last k milliseconds. Instead of re‑scanning the last k packets for each new arrival, the router maintains a monotonic queue of packet sizes, instantly exposing the current peak—a direct analogue to the deque solution.

During an interview, implement the deque logic first for clarity, then add the index‑based eviction check (i - deque.front() >= k) to avoid stale elements. A quick sanity test with a strictly decreasing array confirms the deque never grows beyond k, reinforcing correctness.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(k)

Core Theory — Why This Approach?

The Sliding Window Maximum problem exemplifies the need for amortized O(1) per‑element operations when dealing with contiguous sub‑array queries. A naïve solution recomputes the maximum for each window by scanning k elements, leading to O(n·k) time, which quickly becomes prohibitive for large n (up to 10^5 or more) and k (up to n). The optimal paradigm leverages a double‑ended queue (deque) to maintain candidates for the maximum in a monotonic decreasing order. As the window slides, elements that fall out of the window are evicted from the front, while newly entered elements purge any smaller values from the back, guaranteeing that the deque’s front always holds the current window’s maximum. This monotonic queue technique provides an amortized O(1) update per index, collapsing the overall complexity to O(n).\n\nThe underlying theory rests on two observations: (1) the maximum of a window cannot be smaller than any element that entered later and survived the monotonic purge, and (2) once an element is removed from the deque because a larger element arrived, it will never become the maximum for any future window. These invariants enable a linear‑time solution without auxiliary segment trees or heaps, which would add logarithmic overhead. The approach also scales gracefully to variations such as sliding window minimum, sum, or custom aggregate functions, making it a cornerstone pattern in streaming and real‑time analytics.

Interview Questions on This Problem

Q1How would you modify the deque solution to return the indices of the maximum elements instead of their values?

Store indices in the deque instead of values; when comparing, use nums[deque.back()] <= nums[i] to maintain monotonicity. Before recording the answer for each window, the front of the deque gives the index of the maximum, which can be directly output.

Q2Can you solve Sliding Window Maximum using a segment tree or a binary indexed tree? What are the trade‑offs compared to the deque method?

Yes, build a segment tree where each node stores the maximum of its interval; query each window in O(log n) time, yielding O(n log n) total. The trade‑off is higher memory (≈4n) and slower runtime versus the O(n) deque, though segment trees support arbitrary range queries and updates, useful if the array changes dynamically.

Q3In a distributed log‑processing system, how would you compute the maximum over a moving time‑window of size k seconds across multiple machines?

Partition the stream by time buckets, compute local maxima per bucket using a monotonic queue, then merge overlapping bucket results using a hierarchical reduction (e.g., a sliding window over the aggregated bucket maxima). This mirrors the deque’s amortized O(1) updates while handling data partitioning and network latency.

Examples

Example 1

Input

nums = [4, 2, 12, 3, 8, 7, 5, 10], k = 3

Output

[12, 12, 12, 8, 8, 10]

Explanation: Window positions and their maxima: 1. [4,2,12] → max = 12 2. [2,12,3] → max = 12 3. [12,3,8] → max = 12 4. [3,8,7] → max = 8 5. [8,7,5] → max = 8 6. [7,5,10] → max = 10 Collecting these yields [12,12,12,8,8,10].

Example 2

Input

nums = [-5, -1, -3, -2, -4, -6], k = 2

Output

[-1, -1, -2, -2, -4]

Explanation: Sliding windows of size 2: 1. [-5,-1] → max = -1 2. [-1,-3] → max = -1 3. [-3,-2] → max = -2 4. [-2,-4] → max = -2 5. [-4,-6] → max = -4 Thus the result array is [-1,-1,-2,-2,-4].

Example 3

Input

nums = [9, 7, 5, 3, 1, 2, 4, 6, 8], k = 5

Output

[9,7,5,6,8]

Explanation: The five‑element windows and their maximums are: 1. [9,7,5,3,1] → 9 2. [7,5,3,1,2] → 7 3. [5,3,1,2,4] → 5 4. [3,1,2,4,6] → 6 5. [1,2,4,6,8] → 8 Collecting these values gives [9,7,5,6,8].

Constraints

1 <= nums.length <= 100000
1 <= k <= nums.length
-10^9 <= nums[i] <= 10^9
The algorithm should run in O(n) time and O(k) auxiliary space.

Optimal Approach & Strategy

Use a monotonic decreasing deque to store potential maxima, updating it in amortized O(1) per element as the window slides.

Brute Force Approach

For each window, scan all k elements to find the maximum, repeating this for every possible window start index.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function maxSlidingWindow(nums, k) {
    const deque = []; // will store indices
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        // Remove indices out of the current window
        if (deque.length && deque[0] <= i - k) deque.shift();
        // Remove smaller values from the back
        while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
        deque.push(i);
        // Record max when window is full
        if (i >= k - 1) result.push(nums[deque[0]]);
    }
    return result;
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq; // stores indices
        vector<int> result;
        for (int i = 0; i < (int)nums.size(); ++i) {
            // Remove indices out of the current window
            if (!dq.empty() && dq.front() <= i - k) dq.pop_front();
            // Remove indices whose corresponding values are less than nums[i]
            while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
            dq.push_back(i);
            // Window has hit size k, record the max (front of deque)
            if (i >= k - 1) result.push_back(nums[dq.front()]);
        }
        return result;
    }
};

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> dq = new ArrayDeque<>(); // stores indices
        int[] result = new int[nums.length - k + 1];
        int ri = 0;
        for (int i = 0; i < nums.length; i++) {
            // Remove indices out of the current window
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
            // Remove smaller values from the back
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
            dq.offerLast(i);
            // Record max when window is full
            if (i >= k - 1) {
                result[ri++] = nums[dq.peekFirst()];
            }
        }
        return result;
    }
}

from collections import deque

def max_sliding_window(nums, k):
    """Return list of maximums for each sliding window of size k."""
    if not nums or k == 0:
        return []
    dq = deque()  # stores indices
    result = []
    for i, num in enumerate(nums):
        # Remove indices out of the current window
        if dq and dq[0] <= i - k:
            dq.popleft()
        # Remove indices whose values are less than current num
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        # Append current max to result when window is full
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

function maxSlidingWindow(nums, k) {
    const deque = []; // will store indices
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        // Remove indices out of the current window
        if (deque.length && deque[0] <= i - k) deque.shift();
        // Remove smaller values from the back
        while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
        deque.push(i);
        // Record max when window is full
        if (i >= k - 1) result.push(nums[deque[0]]);
    }
    return result;
}

Asked in Top Tech Interviews

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.