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 Sam K., Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Bloomberg loops.

  • LeetCode (2026)— Problem #239 'Sliding Window Maximum' — canonical statement and bounds; the textbook home of the monotonic-deque pattern.
  • Google Search Console (InterviewChamp) (2026-Q2)— Live search-demand data shows candidates searching this problem paired with Bloomberg interview prep.

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: O(nk) rescanning re-derives information the previous window already proved — at n = 10^5 with a large k it is two orders of magnitude past budget. Name it, quantify it, and move to the deque within a sentence.

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: Amortized O(n): every index enters and leaves the deque at most once. The price is invariant discipline — the deque stores INDICES (so expiry is checkable), in decreasing value order, and both eviction rules must run before reading the front.

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.

Common mistakes

  • Storing values instead of indices in the deque — you then cannot tell when the front has slid out of the window.
  • Evicting smaller elements with <= instead of < (or vice versa) inconsistently — duplicates must keep ONE representative or maxima disappear.
  • Reading the window max before both eviction passes have run — order is expire-front, evict-smaller-back, push, then read.
  • Emitting results from index 0 instead of waiting until the first full window at i = k - 1.

Follow-up questions

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

  • Sliding Window Minimum — flip the deque's ordering comparison; everything else is identical.
  • Shortest Subarray with Sum at Least K (LC 862) — the same monotonic-deque idea applied to prefix sums, a genuine hard.
  • Constrained Subsequence Sum (LC 1425) — monotonic deque powering a DP transition, the next difficulty rung.

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 does the deque give O(n) when there are two nested while loops?

Amortized analysis: each index is pushed exactly once and can be popped at most once across the entire run. Total deque operations are bounded by 2n regardless of how they cluster, so the whole pass is linear.

Why must smaller elements be evicted from the back?

An older element that is smaller than the incoming one can never be a future window maximum — the newer element outlives it AND beats it. Removing those losers is what keeps the front always equal to the current max.

Why not use a max-heap instead?

A heap works but costs O(n log n) and needs lazy deletion of expired indices. The deque achieves strictly better time with simpler expiry — the heap is the answer you give while deriving the deque, not the destination.

More Bloomberg coding interview questions

See all Bloomberg problems →

Companies that also ask Sliding Window Maximum