24. Sliding Window Maximum
hardAsked at IntuitGiven 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 Sam K., 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^41 <= k <= nums.length
Examples
Example 1
nums = [1,3,-1,-3,5,3,6,7], k = 3[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
nums = [1], k = 1[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.
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.