Skip to main content

239. Sliding Window Maximum

mediumAsked at Bloomberg

Bloomberg's risk engine computes rolling maximum drawdown across a moving time window on live price feeds — this problem tests whether you can deliver those rolling stats in O(n) with a monotonic deque instead of rescanning the window each tick.

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

Problem

Given an integer array nums and an integer k, there is a sliding window of size k moving from the left to the right of the array. Return an array of the maximum values in 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: Each window of size 3 has maximums 3, 3, 5, 5, 6, 7.

Example 2

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

Approaches

1. Brute force (rescan each window)

For each window position, scan all k elements to find the maximum. Simple but O(nk) — blows latency budgets on large feeds.

Time
O(nk)
Space
O(1) extra
function maxSlidingWindow(nums, k) {
  const result = [];
  for (let i = 0; i <= nums.length - k; i++) {
    let max = -Infinity;
    for (let j = i; j < i + k; j++) max = Math.max(max, nums[j]);
    result.push(max);
  }
  return result;
}

Tradeoff:

2. Monotonic deque (optimal)

Maintain a deque of indices in decreasing order of their values. The front is always the current window's max. Before adding a new element, evict indices whose values are smaller (they can never be a future max) and those that have fallen out of the window.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const deque = [];
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    while (deque.length && deque[0] < i - k + 1) deque.shift();
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
    deque.push(i);
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

Tradeoff:

Bloomberg-specific tips

Bloomberg scores this on two axes: correctness and real-time viability. The brute-force fails at scale — explicitly say so. For the deque solution, walk through the invariant: 'the deque always holds candidate indices for the current window max in decreasing value order.' Bloomberg interviewers may then ask you to extend it to a sliding window minimum or to emit the full top-K per window — both require only small deque tweaks, so think ahead.

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 Bloomberg interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →