Skip to main content

25. Sliding Window Maximum

hardAsked at Riot Games

Return the maximum of every sliding window of size k — Riot uses monotonic deques to track peak damage or ping spikes within rolling server-tick windows.

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

Problem

Given an array nums and an integer k, return the maximum value of each sliding window of size k as it moves from left to right by one 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]

Example 2

Input
nums=[1], k=1
Output
[1]

Approaches

1. Per-window max scan

Slide the window by one and rescan k elements for the max.

Time
O(n*k)
Space
O(1)
const out = [];
for (let i=0;i<=nums.length-k;i++) {
  let m = -Infinity;
  for (let j=i;j<i+k;j++) m = Math.max(m, nums[j]);
  out.push(m);
}
return out;

Tradeoff:

2. Monotonic decreasing deque

Store indices in a deque so values are monotonically decreasing; evict expired indices from the front and smaller indices from the back. The front is always the window max. Mirrors how Riot tracks peak ping or damage in rolling server-tick windows to flag lag-compensation outliers in O(1) per tick.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const dq = []; // stores indices, values monotonically decreasing
  const out = [];
  for (let i=0;i<nums.length;i++) {
    while (dq.length && dq[0] <= i-k) dq.shift();
    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:

Riot Games-specific tips

Riot expects you to land the monotonic-deque pattern and explain the amortized O(1)-per-element analysis — the same window-max strategy their server uses to flag lag-compensation anomalies inside every tick's rolling latency buffer.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →