Skip to main content

239. Sliding Window Maximum

hardAsked at Twilio

Sliding Window Maximum is Twilio's monotonic-deque probe: given an array nums and window size k, return the max in every k-length window. The grading rubric weighs whether you avoid the O(n * k) naive scan and reach for the monotonic-decreasing-deque trick that yields O(n).

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

Source citations

Public interview reports confirming this problem appears in Twilio loops.

  • Glassdoor (2026-Q1)— Cited in Twilio backend SWE on-site rounds, especially for rate-limiter and stream-processing teams.
  • LeetCode Discuss (2025-12)— Listed in Twilio interview reports as a 'tail-question' after Top K Frequent Elements.

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 max 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]

Approaches

1. Brute-force — scan every window (rejected)

For each window position, scan k elements to find the max.

Time
O(n * k)
Space
O(n)
function maxSlidingWindowBrute(nums, k) {
  const result = [];
  for (let i = 0; i + k <= nums.length; i++) {
    let m = nums[i];
    for (let j = i + 1; j < i + k; j++) {
      if (nums[j] > m) m = nums[j];
    }
    result.push(m);
  }
  return result;
}

Tradeoff: At n = 10^5 and k = 10^4, that's 10^9 ops — TLE. Twilio interviewers want you to name this then immediately discuss the monotonic-deque pattern.

2. Max-heap with lazy deletion (intermediate)

Push each (value, index) into a max-heap; on each window slide, pop entries whose index has slid out.

Time
O(n log n)
Space
O(n)
// Pseudocode — JS doesn't ship a heap; bring one in or use a library
// const heap = new MaxHeap(); heap.push([val, idx])
// while (heap.peek()[1] < i - k + 1) heap.pop()
// result.push(heap.peek()[0])

Tradeoff: O(n log n) — middle ground between brute force and optimal. Each element is pushed once and popped at most once, but each heap op is log n. Real-life answer if you don't remember the deque trick, but Twilio's bar is the linear deque.

3. Monotonic decreasing deque (optimal)

Maintain a deque of indices whose values are in strict decreasing order. The front is always the current window's max.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const result = [];
  const dq = []; // indices, front = max of current window
  for (let i = 0; i < nums.length; i++) {
    // Drop front if it's slid out of the window
    if (dq.length > 0 && dq[0] < i - k + 1) dq.shift();
    // Drop back while it's smaller than the new value
    while (dq.length > 0 && nums[dq[dq.length - 1]] < nums[i]) dq.pop();
    dq.push(i);
    if (i >= k - 1) result.push(nums[dq[0]]);
  }
  return result;
}

Tradeoff: Each index enters and leaves the deque exactly once, giving total work O(n). The invariant 'dq contains a strictly decreasing sequence of values' means the front is always the max of the current window. Beware: dq.shift() is O(n) in JS arrays — use a proper deque for production scale, or an index pointer for the LC constraints.

Twilio-specific tips

Twilio's bar on this question is the monotonic-deque pattern. Walk through the invariant out loud: 'the deque holds indices in strictly decreasing value order, so the front is always the max of any window that contains it'. The two key operations to articulate are (1) drop expired front, (2) drop smaller backs — the rubric explicitly grades whether you can name both. The pattern also shows up in production rate-limiter sliding-window-counter logic; mentioning the domain relevance is a strong signal.

Common mistakes

  • Storing values in the deque instead of indices — you need indices to know when an entry expires from the window.
  • Using `<=` in the back-drop check — duplicate values should both be tracked (or you risk popping the wrong index later).
  • Forgetting the i >= k - 1 guard — the first k-1 iterations are building the initial window and shouldn't emit results.

Follow-up questions

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

  • Sliding window MINIMUM? (Same pattern, monotonic INCREASING deque.)
  • What if you needed the median of each window instead (LC 480)? (Two heaps — max-heap of lower half, min-heap of upper half, balanced.)
  • How would you adapt this to a streaming input where nums is infinite? (Same algorithm — bounded memory because the deque is at most k entries.)

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 does the deque approach achieve O(n) total?

Aggregate analysis. Each index is pushed exactly once and popped at most once across the whole run — so the total deque operations are bounded by 2n, regardless of how many drops happen on any individual step.

Why does this work for both 'max' and 'min'?

It works for any operation whose 'dominance' relation is transitive. For max, a smaller value to the left of a larger value is dominated and can be dropped. For min, larger values to the left of smaller values are dominated.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →