Log inSign up
hardLeetCodeNot Started

Sliding Window Maximum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Queue
Solve on LeetCode
Lesson

Problem Statement

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1 · Standard Sliding Window:

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

Example 2 · Single Element Array:

Input: nums = [1], k = 1
Output: [1]
Explanation: Single window contains 1.

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Deque Mechanics
  • Monotonic Stack / Queue Concepts
  • Sliding Window Basics

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master Monotonic Deque invariant: values decrease monotonically from front to back.
  • Understand why storing indices instead of raw values enables effortless window boundary eviction.
  • Apply amortized linear analysis to multi-element deque purges.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sliding window extreme value queries (min/max).
  • Need O(N) overall runtime where standard priority queue gives O(N log K).

Algorithmic Decision Tree:

  • Maintain a Monotonic Deque storing INDICES.
  • Pop from back while nums[deque.back()] <= nums[i].
  • Pop from front if deque.front() <= i - k.
  • Record nums[deque.front()] once i >= k - 1.

Connected Patterns:

Next Greater ElementDaily TemperaturesShortest Subarray with Sum at Least K

1. Brute Force — Re-Scan Each Window

Intuition

For every window [i, i + k - 1], compute the maximum element with a linear loop.

Algorithm

  1. Step 1: Loop i from 0 to N - K.
  2. Step 2: Find max in nums[i ... i + K - 1].
  3. Step 3: Append max to result array.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<int> maxSlidingWindow(vector<int>& nums, int k) {
10 vector<int> result;
11 int n = nums.size();
12 for (int i = 0; i <= n - k; ++i) {
13 int maxVal = nums[i];
14 for (int j = i; j < i + k; ++j) {
15 maxVal = max(maxVal, nums[j]);
16 }
17 result.push_back(maxVal);
18 }
19 return result;
20 }
21};
22
23int main() {
24 Solution sol;
25 vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
26 vector<int> res = sol.maxSlidingWindow(nums, 3);
27 for (int x : res) cout << x << " ";
28 cout << endl; // 3 3 5 5 6 7
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N * K) — Iterates over K elements for each of the (N - K + 1) windows.
  • Space complexity: O(1) Auxiliary — Output array only.

Why Brute Force Doesn't Scale:

For N = 105 and K = 50,000, brute force takes 5 billion operations (> 10 seconds).

Monotonic deque processes N = 105 in 8 milliseconds.

2. Better — Max-Heap with Lazy Eviction (O(N log N))

Intuition

Insert (nums[i], i) into a Max-Heap. On each step, discard the top element if its index is outside the current window.

Algorithm

  1. Step 1: Push pairs (nums[i], i) into a max-heap.
  2. Step 2: While heap.top().index <= i - k, pop top.
  3. Step 3: Once i >= k - 1, heap.top().val is the window maximum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<int> maxSlidingWindow(vector<int>& nums, int k) {
10 priority_queue<pair<int, int>> pq;
11 vector<int> result;
12
13 for (int i = 0; i < nums.size(); ++i) {
14 pq.push({nums[i], i});
15
16 while (pq.top().second <= i - k) {
17 pq.pop();
18 }
19
20 if (i >= k - 1) {
21 result.push_back(pq.top().first);
22 }
23 }
24 return result;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
31 vector<int> res = sol.maxSlidingWindow(nums, 3);
32 for (int x : res) cout << x << " ";
33 cout << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N log N) — Pushing N items into heap takes O(N log N). Lazy eviction pops invalid tops.
  • Space complexity: O(N) — Heap holds at most N elements.

3. Optimal — Monotonic Decreasing Deque (Linear O(N))

Intuition

Keep indices in a double-ended queue. Maintain values in strictly descending order. If incoming element > back of deque, pop back. Deque front is guaranteed to be window maximum.

Algorithm

  1. Step 1: Initialize an empty deque dq storing indices.
  2. Step 2: For each index i from 0 to n - 1:
  3. Step 3: Remove expired indices from front: while (!dq.empty() && dq.front() <= i - k) dq.pop_front().
  4. Step 4: Maintain monotonicity: while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back().
  5. Step 5: dq.push_back(i).
  6. Step 6: If i >= k - 1, append nums[dq.front()] to result.

Monotonic Deque Trace

2 of 2 questions left today
Step 1 / 8
Trace timeline13% explored
Current operationSTEP 1 OF 8
dq: [0]
Visual state
Values and pointers at this exact step
queue
FRONT → REAR
idx 0 (val 1)
Enqueue adds at the rear · Dequeue removes from the front
Decision / next transition
i = 0 (val 1)
Why this step matters

dq: [0]

Step 1 / 8
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <deque>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<int> maxSlidingWindow(vector<int>& nums, int k) {
10 deque<int> dq;
11 vector<int> result;
12 int n = nums.size();
13
14 for (int i = 0; i < n; ++i) {
15 // 1. Remove indices outside current window
16 while (!dq.empty() && dq.front() <= i - k) {
17 dq.pop_front();
18 }
19
20 // 2. Remove smaller elements from back (monotonic decreasing)
21 while (!dq.empty() && nums[dq.back()] <= nums[i]) {
22 dq.pop_back();
23 }
24
25 // 3. Push current index
26 dq.push_back(i);
27
28 // 4. Record front as maximum once first window is formed
29 if (i >= k - 1) {
30 result.push_back(nums[dq.front()]);
31 }
32 }
33 return result;
34 }
35};
36
37int main() {
38 Solution sol;
39 vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
40 vector<int> res = sol.maxSlidingWindow(nums, 3);
41 for (int x : res) cout << x << " ";
42 cout << endl; // 3 3 5 5 6 7
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N) — Every element is pushed to the deque once and popped at most once. Across N iterations, total time is O(2N) = O(N).
  • Space complexity: O(K) Deque Memory — The deque holds at most K indices for the active window.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear Scan per WindowO(N * K)O(1) AuxiliaryFor every window starting at index i, loop k times to find the maximum value.Re-scanning all K elements for every 1-step window slide.
2.Better — Max-Heap / Priority Queue with Lazy EvictionO(N log N)O(N)Store pairs (val, index) in a Max-Heap. Peek top and discard if index is outside the window.O(log N) heap insertion and eviction.
3.Optimal — Monotonic Decreasing Deque (Amortized O(1))OptimalO(N)O(K)Double-ended queue of indices in strictly decreasing value order. Front is always the maximum.None. Each index is pushed and popped at most once.

Common Pitfalls & Crucial Edge Cases

Storing values instead of indices in deque

Storing raw values makes it impossible to know when an element has fallen outside the i - k boundary.

Using strict `<` instead of `<=` when popping from back

Popping elements <= keeps duplicate maximums cleanly pruned.

Crucial Edge Cases to Validate:

  • K == 1 — Every element is its own window maximum; deque processes each element independently.
  • K == N — Single window covering entire array; returns single global maximum.
  • Strictly decreasing array (e.g. [5, 4, 3, 2, 1]) — Deque retains all K indices in window without popping from back.
  • Strictly increasing array (e.g. [1, 2, 3, 4, 5]) — Each new element empties all previous items in deque.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the core Monotonic invariant immediately: 'I will maintain a monotonic decreasing deque of indices so the maximum is always at the front in O(1).'
  2. Explain amortized complexity: 'Although a while loop exists inside the for loop, each element is pushed once and popped once, giving strict O(N) aggregate time.'
  3. Always mention why storing indices in the deque is necessary for O(1) sliding window boundary checks.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we store indices rather than values in the monotonic deque?

2.What is the amortized time complexity of the monotonic deque approach?

3.In what order are values maintained in the deque from front to back?

Back to DSA Sheet