80. Sliding Window Maximum
hardAsked at WorkdayReturn the maximum in each sliding window of size k. Workday uses this for monotonic-deque fluency — same shape as computing peak headcount over a rolling pay-period window.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Workday loops.
- Glassdoor (2026-Q1)— Workday SDE3 onsite.
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^41 <= k <= nums.length
Examples
Example 1
nums = [1,3,-1,-3,5,3,6,7], k = 3[3,3,5,5,6,7]Example 2
nums = [1], k = 1[1]Approaches
1. Brute force per window
For each window, scan for max.
- Time
- O(n * k)
- Space
- O(1)
// nested loop maxTradeoff: Too slow at n=10^5, k=large.
2. Monotonic deque
Maintain a deque of indices with monotonically decreasing values. Front is the max.
- Time
- O(n)
- Space
- O(k)
function maxSlidingWindow(nums, k) {
const result = [];
const dq = []; // stores indices
for (let i = 0; i < nums.length; i++) {
while (dq.length > 0 && dq[0] <= i - k) dq.shift();
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 element enters and leaves the deque once — amortized O(n). Front always holds the current window's max.
Workday-specific tips
Workday wants the monotonic deque. The two while loops (drop out-of-window from front; pop smaller from back) are the entire pattern. Walk through with [1,3,-1] before coding.
Common mistakes
- Storing values instead of indices — can't tell when to drop out-of-window.
- Using nums[dq[0]] <= nums[i] (instead of <) — pops equal values, still correct but slightly wasteful.
- Emitting result before window is fully formed — first k-1 indices have no result.
Follow-up questions
An interviewer at Workday may pivot to one of these next:
- Sliding Window Minimum — flip the comparison.
- Sliding Window Median (LC 480).
- What if k can change over time?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why store indices?
We need to know when an entry falls out of the window. The index lets us compare against i - k.
Amortized O(n)?
Each element enters the deque exactly once and exits at most once. Total work across all iterations is O(n).