Skip to main content

80. Sliding Window Maximum

hardAsked at Workday

Return 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 Alex Chen, 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^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 per window

For each window, scan for max.

Time
O(n * k)
Space
O(1)
// nested loop max

Tradeoff: 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.

Output

Press Run or Cmd+Enter to execute

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).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →