Skip to main content

24. Sliding Window Maximum

hardAsked at Intuit

Given an integer array and a window size k, return the maximum of each contiguous k-sized window. Intuit asks this for senior coding rounds and reframes it as 'running max-balance over a rolling N-day window in a ledger.'

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

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2026-Q1)— Intuit SWE III onsite — monotonic deque under the 'rolling max balance' framing.
  • LeetCode Discuss (2025-11)— Intuit senior coding loop — interviewer pressed for O(n) over O(n log k).

Problem

You are given an array of integers nums, and 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 — the maximum element in each 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 per-window scan

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

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

Tradeoff: O(n*k) — TLEs on n=10^5, k=10^4. Mention then propose deque.

2. Monotonic deque (optimal)

Maintain a deque of indices where nums values are strictly decreasing front-to-back. The front is always the max of the current window. Pop from back when adding a larger value; pop from front when the index falls outside the window.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const dq = []; // indices, nums values strictly decreasing front-to-back
  const out = [];
  for (let i = 0; i < nums.length; i++) {
    // pop indices that fall out of the window
    while (dq.length && dq[0] <= i - k) dq.shift();
    // pop smaller-or-equal values from the back
    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: Each index enters and leaves the deque at most once → amortized O(1) per step. Use a head-index ring buffer if dq.shift() O(n) is a concern in production.

Intuit-specific tips

Intuit asks this for QuickBooks reporting — rolling 7-day or 30-day max-balance over millions of ledger entries. They grade for the monotonic-deque invariant statement upfront ('indices, with nums values strictly decreasing'). They probe whether you remember to evict by index, not by value (a common subtle bug). Bonus signal: discuss the sliding-window median variant (LC 480) which needs two heaps instead of a deque.

Common mistakes

  • Storing values in the deque instead of indices — can't tell when an entry exits the window.
  • Using < vs <= when popping from the back — affects whether you keep duplicates (it should be <).
  • Using array.shift() in a hot loop — it's O(n) per call in JavaScript; use a head pointer for true O(n).

Follow-up questions

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

  • Sliding Window Median (LC 480).
  • Shortest Subarray with Sum at Least K (LC 862) — monotonic deque on prefix sums.
  • What if k is variable per query? Use a segment tree.

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 strictly decreasing and not non-increasing?

Strictly decreasing ensures we never keep stale duplicates. If we use <=, equal values evict the older index, which is fine here (we only need the max), but using < works equally well and matches more invariants in related problems.

How does this map to a financial use case?

Rolling max-balance over a window is a stress-test signal in QuickBooks — 'did any 30-day window exceed the credit ceiling?' Monotonic deque computes all such maxima in one O(n) pass over millions of transactions.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →