239. Sliding Window Maximum
hardAsked at RobinhoodGiven an array and a window size k, return an array of the maximum in each sliding window of size k. Robinhood asks this because rolling-max patterns power high-watermark queries in market-data analytics and order-book monitoring.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Robinhood loops.
- Glassdoor (2026-Q1)— Robinhood SWE-II onsite reports include Sliding Window Maximum as a recurring hard round.
- Blind (2025-11)— Robinhood backend trip reports describe rolling-window aggregations as a thematic favorite.
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 — an array of the maximum value in each window position.
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 window scan
For each window position, scan the k elements and take the max.
- Time
- O(n*k)
- Space
- O(1)
function maxSlidingWindowBrute(nums, k) {
const result = [];
for (let i = 0; i <= nums.length - k; i++) {
let max = -Infinity;
for (let j = i; j < i + k; j++) {
if (nums[j] > max) max = nums[j];
}
result.push(max);
}
return result;
}Tradeoff: O(n*k) — too slow for n=10^5, k=10^5. Use as the verbal warm-up before moving to the deque.
2. Monotonic deque (optimal)
Maintain a deque of indices whose values are strictly decreasing. The front is the max of the current window. Pop from the back if a new element is larger; pop from the front if it's out of window.
- Time
- O(n)
- Space
- O(k)
function maxSlidingWindow(nums, k) {
const result = [];
const dq = []; // indices, values decreasing front-to-back
for (let i = 0; i < nums.length; i++) {
// Pop out-of-window indices from front
while (dq.length && dq[0] <= i - k) dq.shift();
// Pop smaller-than-current from back
while (dq.length && nums[dq[dq.length - 1]] < nums[i]) dq.pop();
dq.push(i);
if (i >= k - 1) result.push(nums[dq[0]]);
}
return result;
}Tradeoff: True O(n) — each index is pushed and popped at most once. The deque invariant (strictly decreasing) guarantees the front is always the window max. Use a real deque structure for shift in O(1) on the front.
3. Max-heap with lazy deletion
Push (value, index) pairs into a max-heap. On window slide, lazy-delete the top while its index is out of window.
- Time
- O(n log n)
- Space
- O(n)
class MaxHeap {
constructor() { this.data = []; }
size() { return this.data.length; }
peek() { return this.data[0]; }
push(v) { this.data.push(v); this._up(this.data.length - 1); }
pop() { const top = this.data[0]; const last = this.data.pop(); if (this.data.length) { this.data[0] = last; this._down(0); } return top; }
_up(i) { while (i > 0) { const p = (i - 1) >> 1; if (this.data[p][0] >= this.data[i][0]) break; [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p; } }
_down(i) { const n = this.data.length; while (true) { const l = 2*i+1, r = 2*i+2; let best = i; if (l < n && this.data[l][0] > this.data[best][0]) best = l; if (r < n && this.data[r][0] > this.data[best][0]) best = r; if (best === i) break; [this.data[best], this.data[i]] = [this.data[i], this.data[best]]; i = best; } }
}
function maxSlidingWindowHeap(nums, k) {
const heap = new MaxHeap();
const result = [];
for (let i = 0; i < nums.length; i++) {
heap.push([nums[i], i]);
if (i >= k - 1) {
while (heap.peek()[1] <= i - k) heap.pop();
result.push(heap.peek()[0]);
}
}
return result;
}Tradeoff: O(n log n) — easier to think about than the deque, but slower. Useful when the interviewer wants to see a heap-based solution as a comparison.
Robinhood-specific tips
Robinhood interviewers want to hear the deque invariant explained: 'we maintain a deque where values are strictly decreasing front-to-back, so the front is always the window max.' Then code carefully. If you fumble the deque, the heap-with-lazy-deletion fallback is acceptable but slower. Use Array as a deque with care — Array.shift is O(n) in some engines; for true O(n) total cost, track a head pointer or use a real deque class.
Common mistakes
- Using Array.shift on a long array — degrades to O(n^2) in some JS engines.
- Strict less-than (<) vs less-or-equal (<=) when popping the back — < is correct for keeping the leftmost max if there are duplicates.
- Pushing values instead of indices — you need indices to check if the front is out of the window.
Follow-up questions
An interviewer at Robinhood may pivot to one of these next:
- Sliding-Window Median (LC 480) — extends to two-heap with lazy deletion.
- Sliding-Window Sum — running sum + remove-as-you-slide.
- Window of variable size — generalize the deque pattern.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why a deque and not a heap?
Heap is O(n log n) because every insert is log n. Deque is O(n) because each index is pushed and popped at most once. Deque is the optimal.
What does 'monotonic' mean here?
The deque's values are strictly decreasing front-to-back. So the front is always the largest. Adding a new element triggers back-pops of anything smaller (they can never be the max while the new element is in window).
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Sliding Window Maximum and other Robinhood interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →