Skip to main content

239. Sliding Window Maximum

hardAsked at Akamai

Return the maximum value in each sliding window of size k. Akamai uses this as a real-time analytics primitive — computing peak request rates, maximum connection counts, or highest latency values in a rolling time window across edge server telemetry is exactly this algorithm at production scale.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2026-Q1)— Akamai SWE reports list Sliding Window Maximum as a hard problem asked to test deque-based monotonic data structure knowledge.
  • Blind (2025-11)— Akamai threads confirm this is asked with explicit expectation of the O(n) deque solution over O(n log n) heap alternatives.

Problem

You are given an array of integers nums and an integer k. 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 maximum sliding window. Return an array of the maximum values for each window position.

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: Window [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]

Explanation: Single element window.

Approaches

1. Monotonic deque (O(n))

Maintain a deque of indices in decreasing order of their values. The front of the deque is always the index of the maximum in the current window. When adding a new element, pop from the back all indices whose values are <= the new element (they can never be the maximum while the new element is in the window). Pop from the front any index that has fallen outside the window.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const deque = []; // stores indices, front = max of current window
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside the current window
    while (deque.length && deque[0] < i - k + 1) deque.shift();
    // Remove indices whose values are <= nums[i] (they are useless)
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) deque.pop();
    deque.push(i);
    // Add to result once the first full window is formed
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

Tradeoff: O(n) time, O(k) space. Each element is pushed and popped from the deque at most once, giving amortized O(1) per element. This is the optimal solution and the one Akamai expects.

2. Max-heap (O(n log k))

Maintain a max-heap of (value, index) pairs. Pop stale entries from the top (those outside the window) before recording each window maximum.

Time
O(n log k)
Space
O(k)
// JavaScript has no built-in max-heap; sketch the approach:
// 1. Use a sorted structure (or simulate with sort + array slicing for small k).
// 2. For each window, push (nums[i], i); pop while top index < i-k+1.
// 3. Top is window max.
// Full max-heap implementation omitted for brevity; deque is preferred.
function maxSlidingWindow(nums, k) {
  // Brute force O(n*k) for illustration only:
  const result = [];
  for (let i = 0; i <= nums.length - k; i++) {
    result.push(Math.max(...nums.slice(i, i + k)));
  }
  return result;
}

Tradeoff: O(n log k) with a true heap. The brute-force above is O(n*k). Present the heap approach verbally and pivot to the deque as the O(n) optimal solution.

Akamai-specific tips

Name the data structure before writing code: 'I need a monotonic decreasing deque — a deque where elements are always in decreasing order of value. The invariant is: deque[front] is always the index of the maximum element in the current window.' Akamai interviewers specifically test whether candidates know the name 'monotonic deque' and can state the invariant precisely. Connect to production: 'At 10^9 data points per day, O(n) is mandatory — O(n log n) with a heap would be 30× slower.'

Common mistakes

  • Storing values instead of indices in the deque — you can't evict elements outside the window without knowing their position.
  • Not evicting from the front before recording the window maximum — the deque front may be stale (outside the window).
  • Using <= instead of < in the back-eviction condition — elements equal to nums[i] should be removed (they will never be chosen over nums[i] while it is in the window).

Follow-up questions

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

  • Sliding Window Minimum — symmetric: use a monotonic increasing deque.
  • Minimum Window Substring (LC 76) — find the smallest window containing all required characters.
  • How would you compute the sliding maximum on a data stream where elements are evicted by TTL rather than by a fixed window size?

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 is the deque monotonic decreasing?

If nums[i] >= nums[j] and j < i, then j will exit the window before i. Whenever i is in the window, j can never be the maximum. So we evict j from the deque as soon as i is added. This invariant means the front is always the current maximum.

Why store indices and not values?

We need to evict elements that have fallen outside the window. Values don't carry position information — only indices do.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →