Skip to main content

239. Sliding Window Maximum

hardAsked at Citadel

Sliding Window Maximum is practically the interview problem for Citadel's trading systems domain — computing the rolling maximum price, maximum volume, or maximum order size over a fixed window is a core operation in market microstructure analytics. The monotonic deque solution is the expected answer; a sorted structure or brute force is insufficient.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Citadel loops.

  • Glassdoor (2026-Q1)— Citadel SWE candidates across multiple years report Sliding Window Maximum as one of the most domain-relevant hard problems in their on-site rounds.
  • Blind (2025-11)— Citadel SWE threads consistently name Sliding Window Maximum as a must-know for the trading systems SWE track — the deque solution is considered baseline knowledge.

Problem

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 maximum of the current window. Return the maximums of each window as an array.

Constraints

  • 1 <= nums.length <= 10^5
  • −10^4 <= nums[i] <= 10^4
  • 1 <= k <= nums.length

Examples

Example 1

Input
nums = [1,3,-1,-3,5,3,6,7], k = 3
Output
[3,3,5,5,6,7]

Explanation: Window [1,3,-1]→3, [3,-1,-3]→3, [-1,-3,5]→5, [-3,5,3]→5, [5,3,6]→6, [3,6,7]→7.

Example 2

Input
nums = [1], k = 1
Output
[1]

Explanation: Single element window.

Approaches

1. Brute force (O(nk))

For each window position, scan all k elements to find the maximum. Correct but too slow for large inputs.

Time
O(nk)
Space
O(1)
function maxSlidingWindow(nums, k) {
  const result = [];
  for (let i = 0; i <= nums.length - k; i++) {
    let max = -Infinity;
    for (let j = i; j < i + k; j++) max = Math.max(max, nums[j]);
    result.push(max);
  }
  return result;
}

Tradeoff: O(nk) — for n = 10^5 and k = 10^4, that's 10^9 operations. Unacceptable at Citadel. Present as the baseline, then immediately pivot to the deque approach.

2. Monotonic deque (O(n))

Maintain a double-ended queue of indices, front-to-back in decreasing order of nums values. The front is always the index of the window maximum. On slide: (1) remove front if out of window. (2) pop from back all indices with values ≤ current. (3) push current. (4) front is the window max.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const result = [];
  const deque = []; // stores indices, front = max of current window

  for (let i = 0; i < nums.length; i++) {
    // Remove indices that are out of the current window
    if (deque.length && deque[0] < i - k + 1) deque.shift();

    // Remove indices from the back whose values are <= nums[i]
    // They can never be the maximum while nums[i] is in the window
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }

    deque.push(i);

    // Start recording results once the first full window is formed
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

Tradeoff: O(n) total — each index is pushed and popped at most once. The deque maintains a decreasing sequence of values, so the front is always the window maximum. This is the canonical O(n) answer and the expected solution at Citadel.

Citadel-specific tips

Explain the deque invariant before writing a single line: 'The deque stores indices of candidate maximums in decreasing order of their values. When a new element arrives, it dominates any smaller element behind it in the window — those smaller elements can never be the maximum while the new element is present, so remove them from the back.' This is the key insight. Citadel will ask: 'How does this map to a real trading system?' Answer: 'Rolling maximum bid over a k-tick window. Each new tick either dominates earlier bids (remove from back) or is dominated by an existing one (just push). The front is always the current rolling maximum — O(1) query, O(1) amortized update.'

Common mistakes

  • Using a sorted data structure (TreeMap or sorted array) instead of a deque — O(n log k) time, valid but not optimal and not the expected answer.
  • Removing from the front before checking if the deque is empty — throws an error on an empty deque.
  • Using <= instead of < when removing dominated elements from the back — using strict < would retain duplicates that are never the max while the current element is in the window.
  • Starting to record results at i >= k instead of i >= k - 1 — off-by-one that produces one fewer result than expected.

Follow-up questions

An interviewer at Citadel may pivot to one of these next:

  • Sliding Window Minimum — same deque approach but maintain an increasing sequence.
  • Sliding Window Median (LC 480) — requires two heaps and an O(log k) removal mechanism.
  • How would you compute the sliding window maximum over a live stream where k is variable?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why store indices instead of values in the deque?

To determine whether the front element has left the window (index < i - k + 1). If you only stored values, you'd have no way to know which window position they correspond to.

What is the deque invariant in one sentence?

The deque contains indices whose corresponding values are in decreasing order, and all indices are within the current window [i-k+1, i].

Can this be done with a max-heap?

Yes — O(n log k). Use a max-heap of [value, index] pairs. On each step, pop the top while its index is out of the window. This is valid but O(n log k) vs O(n) for the deque. Citadel expects the deque.

Practice these live with InterviewChamp.AI

Drill Sliding Window Maximum and other Citadel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →