Blind Plus 100 Visualized

#79 · Sliding Window

Sliding Window Maximum

Given an integer array nums and a window size k that slides from the far left to the far right one position at a time, return the maximum of each window.

HardLeetCode
  • Active
  • Found
  • Window
  • Visited
  • Rejected
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Monotonic deque

A double-ended queue of indices whose values decrease from front to back. The front is the current window maximum; a new element removes every smaller element from the back (they are older and smaller, so they can never win again), and the front is dropped when it leaves the window.

Memory layout

A ring buffer or linked blocks holding at most k indices; storing indices (not values) lets you test whether the front is still inside the window.

OperationCost
push / pop at either endO(1)
total over the arrayO(n) amortised

Block prefix / suffix maxima

Split the array into blocks of size k. Any window is a suffix of one block followed by a prefix of the next, so its maximum is the larger of two precomputed numbers.

Memory layout

Two arrays of length n, filled by sequential passes (cache friendly, easy to vectorise).

OperationCost
buildO(n)
query per windowO(1)

Why it fits

  • Only the candidates that could still become a maximum matter: an element that is smaller than a newer element can never be the answer again, which is exactly what a decreasing deque maintains.
  • Each index is pushed once and popped at most once, so the nested while loop is still O(n) overall.
  • The block decomposition reaches the same bound without a queue by turning a sliding query into two fixed-size aggregates.

Why alternatives degrade

Max-heap with lazy deletion:
Works, but costs O(n log n) and the heap can hold stale entries until they reach the top.
Balanced BST / multiset:
O(n log k): correct but slower and heavier than the deque for a pure maximum.
Segment tree / sparse table:
O(n log n) build, overkill when queries are windows that move one step at a time.

Four approaches, from naive to production

1 · beginner

Scan every window

time O(n · k)space O(1) extra

For each window start, scan its k elements for the largest and append it to the result.

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    int n = nums.size();
    for (int i = 0; i + k <= n; i++) {
        int best = nums[i];
        for (int j = i + 1; j < i + k; j++) best = max(best, nums[j]);
        result.push_back(best);
    }
    return result;
}

Flaws & bottlenecks

  • Rescans almost the same k elements for adjacent windows.
  • With n = 10⁵ and k = 5·10⁴ that is billions of comparisons.
  • Does not use the fact that windows overlap.

Interviewer cross-questions

What is the output length?

Say: n − k + 1 windows, so n − k + 1 values.

What if k = 1 or k = n?

Say: k = 1 returns the array itself; k = n returns a single value, the global maximum.

How can the overlap be exploited?

Say: Between adjacent windows only one element leaves and one enters; a deque of candidates avoids rescanning.

2 · intermediate

Sorted window with binary search

time O(n · k) worst case (O(n log k) with a balanced tree)space O(k)

Keep the current window as a sorted list. Insert the incoming value and remove the outgoing one by binary search; the maximum is the last element.

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    vector<int> window;
    for (int i = 0; i < (int)nums.size(); i++) {
        window.insert(lower_bound(window.begin(), window.end(), nums[i]), nums[i]);
        if (i >= k) window.erase(lower_bound(window.begin(), window.end(), nums[i - k]));
        if (i >= k - 1) result.push_back(window.back());
    }
    return result;
}

Flaws & bottlenecks

  • Array insertion and deletion shift up to k elements.
  • A balanced tree or multiset gets O(log k) updates but is heavier to implement.
  • Maintains the full order when only the maximum is needed.

Interviewer cross-questions

Why keep the whole window sorted?

Say: It gives easy removal of an arbitrary outgoing element; a plain max variable cannot be updated once its holder leaves.

How would a heap compare?

Say: A max-heap of (value, index) with lazy deletion gives O(n log n): pop while the top index is outside the window.

Do duplicates matter?

Say: Removing by value is safe because equal values are interchangeable in a sorted list; any one copy can go.

3 · advanced

Monotonic deque of indices

time O(n)space O(k)

Maintain a deque of indices with decreasing values. Drop the front if it left the window, pop smaller values from the back, push the new index, and read the maximum from the front.

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> dq;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) result.push_back(nums[dq.front()]);
    }
    return result;
}

Flaws & bottlenecks

  • Array.shift is O(k) in most runtimes: use a real deque, ring buffer or head index.
  • The index-versus-value distinction is easy to get wrong.
  • The amortised argument (each index pushed and popped once) needs to be explained.

Interviewer cross-questions

Why can you discard smaller older elements?

Say: A smaller element that arrived earlier leaves the window sooner than the newer, larger element, so it can never be the maximum again.

Why store indices and not values?

Say: You need the index to know when the front has slid out of the window.

How do you handle equal values?

Say: Pop only strictly smaller values (as here), or pop equal ones too; both are correct, since an older equal value expires first.

4 · expert

Block prefix and suffix maxima

time O(n)space O(n)

Split into blocks of size k. Precompute left[i] (max from the block start to i) and right[i] (max from i to the block end). Each window maximum is max(right[start], left[end]).

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    if (n == 0 || k <= 0) return {};
    vector<int> left(n), right(n);
    for (int i = 0; i < n; i++) {
        left[i] = (i % k == 0) ? nums[i] : max(left[i - 1], nums[i]);
    }
    for (int i = n - 1; i >= 0; i--) {
        right[i] = (i == n - 1 || (i + 1) % k == 0) ? nums[i] : max(right[i + 1], nums[i]);
    }
    vector<int> result;
    for (int i = 0; i + k <= n; i++) result.push_back(max(right[i], left[i + k - 1]));
    return result;
}

Flaws & bottlenecks

  • Two extra arrays of length n (the deque version needs only O(k)).
  • Needs the whole array up front: it is not a streaming algorithm.
  • The block boundary arithmetic is easy to get off by one.

Interviewer cross-questions

Why does any window span at most two blocks?

Say: A window has size k and blocks have size k, so it either equals a block or crosses exactly one boundary.

When would you prefer this over the deque?

Say: When you want branch-free, vectorisable passes or need to answer many queries of the same width; for streaming input use the deque.

What are the edge cases?

Say: Empty array or k ≤ 0 returns an empty list; k = 1 gives the array; k ≥ n gives a single global maximum (treat k > n as n if the API allows it).

Synchronized code walkthrough

Showing: Scan every window — shares the player above; click any step to jump.

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    int n = nums.size();
    for (int i = 0; i + k <= n; i++) {
        int best = nums[i];
        for (int j = i + 1; j < i + k; j++) best = max(best, nums[j]);
        result.push_back(best);
    }
    return result;
}