Skip to main content

239. Sliding Window Maximum

hardAsked at Anduril

Find the maximum value in each sliding window of size k across an array. Anduril asks this hard problem because the monotonic deque pattern — maintaining a decreasing deque of candidates — is a precise data-structure technique that appears in real-time signal processing, where you need the running maximum of a bounded time window without reprocessing old data.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2026-Q1)— Listed in Anduril SWE onsite reports as a hard problem testing monotonic deque knowledge for real-time data processing roles.
  • Blind (2025-12)— Multiple Anduril candidate threads cite Sliding Window Maximum as a hard problem that separates strong from average candidates in algorithm rounds.

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 sliding window.

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: Windows: [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

For each window position, compute the max by scanning k elements. O(n*k) time.

Time
O(n*k)
Space
O(1) extra
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(n*k). Unacceptable for large inputs. Present to establish correctness then upgrade immediately.

2. Monotonic deque (O(n))

Maintain a deque of indices in decreasing order of their values. The front is always the index of the window's maximum. Remove indices that leave the window; pop from the back any indices with values smaller than the current element.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const deque = []; // stores indices, front = max of current window
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside the window
    while (deque.length && deque[0] < i - k + 1) deque.shift();
    // Remove indices whose values are smaller than nums[i] — they can never be the max
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
    deque.push(i);
    // Start recording results once the first window is full
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

Tradeoff: O(n) — each element is pushed and popped at most once. The deque maintains the monotonic decreasing invariant: the front is always the index of the maximum in the current window. This is the canonical O(n) solution and what Anduril expects.

Anduril-specific tips

State the deque invariant before coding: 'I maintain a deque of indices where the values are strictly decreasing. The front is always the maximum of the current window. When a new element arrives, I pop all back entries with smaller values — they can never be a future maximum.' Anduril engineers appreciate this level of invariant-first reasoning. Mention that each element is pushed and popped at most once, so the total work is O(n) despite the nested loops. Connect to real systems: this pattern is used in sensor peak-detection pipelines with fixed-length time windows.

Common mistakes

  • Storing values instead of indices in the deque — you need indices to check whether the front has expired (left the window).
  • Removing from the front based on value comparison instead of index comparison — out-of-window removal must use the index, not the value.
  • Recording a result before the first window is complete — only start pushing to result when i >= k - 1.
  • Using '<' instead of '<=' in the monotonic decrease check — equal values should also trigger removal from the back to avoid stale max candidates.

Follow-up questions

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

  • Sliding Window Minimum — the same deque approach with the ordering reversed.
  • How would you compute the sliding window maximum for a stream where k is not fixed?
  • Constrained Subsequence Sum (LC 1425) — uses the same monotonic deque pattern in a DP context.

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 is this O(n) if there are two while loops inside the for loop?

Each element is added to the deque exactly once and removed at most once. Total push + pop operations across all iterations = O(n). The nested while loops do not add a multiplicative factor.

Why store indices instead of values?

The deque front expires when its index falls outside the current window [i-k+1, i]. Without the index, you can't tell whether a value is still in scope.

What if k equals the array length?

The deque processes all elements, the front after the last iteration is the global maximum, and result has exactly one entry. The algorithm handles this correctly.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →