Skip to main content

239. Sliding Window Maximum

hardAsked at JPMorgan

For an array and window size k, return the maximum of each contiguous k-window. JPMorgan asks this on senior SDE and quant-tech loops because the monotonic-deque solution is the canonical example of amortised O(n) and maps directly to streaming-max on a tick feed.

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

Source citations

Public interview reports confirming this problem appears in JPMorgan loops.

  • Glassdoor (2026-Q1)— Recurring JPMorgan senior SDE and quant-tech onsite problem in 2026-Q1 reviews.
  • LeetCode (2026-Q1)— Tagged JPMorgan on the LeetCode company tag page.
  • Blind (2025-12)— JPMC quant-dev write-up: 'monotonic deque, the streaming version was the real grading axis'.

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]

Example 2

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

Approaches

1. Brute force max per window

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

Time
O(n * k)
Space
O(1)
function maxSlidingWindowBrute(nums, k) {
  const out = [];
  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];
    out.push(m);
  }
  return out;
}

Tradeoff: Easiest to write but TLEs at n=10^5 with k near n. Useful only as a baseline.

2. Max-heap with lazy deletion

Push (value, index) into a heap. On query, pop entries whose index falls outside the window. The heap top is the current max.

Time
O(n log n)
Space
O(n)
// Sketch — JavaScript has no built-in heap so the production answer below uses the deque instead.
function maxSlidingWindowHeap(nums, k) {
  const heap = []; // pretend this is a max-heap of [value, index]
  const out = [];
  for (let i = 0; i < nums.length; i++) {
    heap.push([nums[i], i]);
    heap.sort((a, b) => b[0] - a[0]); // pretend O(log n) push
    if (i >= k - 1) {
      while (heap[0][1] <= i - k) heap.shift();
      out.push(heap[0][0]);
    }
  }
  return out;
}

Tradeoff: O(n log n) — passable but slower than the deque. Useful when the deque insight does not click, or when you need percentile/top-k instead of just max.

3. Monotonic deque (optimal, amortised O(n))

Maintain a deque of indices whose values are monotonically decreasing. Before pushing, pop from the back while the back's value <= current. Pop from the front when its index falls outside the window. Front of deque is the current max.

Time
O(n) amortised
Space
O(k)
function maxSlidingWindow(nums, k) {
  const dq = []; // store indices; nums at these indices are strictly decreasing
  const out = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && dq[0] <= i - k) dq.shift();
    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);
    if (i >= k - 1) out.push(nums[dq[0]]);
  }
  return out;
}

Tradeoff: O(n) amortised because each index is pushed once and popped at most once. O(k) space for the deque. This is the answer JPMorgan interviewers want; mention the amortisation argument when you describe correctness.

JPMorgan-specific tips

JPMorgan quant-tech and senior-SDE interviewers explicitly grade two things: (1) the monotonic-decreasing invariant; (2) the amortisation argument (each index touched at most twice — push once, pop once — total O(n)). State both before coding. The streaming follow-up almost always lands: 'now imagine ticks arrive one at a time and you must emit max-of-last-k after every tick' — same algorithm, just emit on each insert.

Common mistakes

  • Using a Set for membership inside the deque — wrong data structure; the deque holds indices in arrival order.
  • Storing values instead of indices — cannot then detect when the front falls outside the window.
  • Forgetting the index-expiry pop at the front of each iteration — produces stale maxima.
  • Popping the back with strict < instead of <= — works but keeps redundant equal values in the deque.

Follow-up questions

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

  • Sliding window minimum (mirror — flip the comparison).
  • Sliding window median (LC 480) — two heaps or a sorted multiset.
  • Maximum of all subarrays of size k (same problem, different phrasing).
  • Streaming variant: emit max-of-last-k after every arriving tick.

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 the monotonic deque amortised O(n)?

Each index is pushed onto the deque exactly once and popped at most once. The two while-loops look like nested loops but their total work across the whole input is at most 2n. Therefore the overall cost is O(n), even though any single iteration can do up to O(k) pop work.

Can you do this in worst-case O(n) instead of amortised?

Not in the comparison model — every position must be inspected at least once. The deque algorithm is worst-case O(n) total work; only the per-iteration cost is variable. So 'amortised O(n)' is overly cautious; the algorithm is in fact O(n) total.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →