Skip to main content

23. Sliding Window Maximum

hardAsked at Coinbase

Extract the peak price across every k-candle trading window in O(n) — Coinbase uses this problem to stress-test whether you can maintain a monotonic deque instead of repeatedly scanning a window when computing rolling highs on order-book snapshots.

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

Problem

Given an integer array nums and an integer k, return an array containing the maximum value of each contiguous subarray of length k as the window slides from left to right.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= k <= nums.length
  • -10^4 <= nums[i] <= 10^4

Examples

Example 1

Input
nums = [1,3,-1,-3,5,3,6,7], k = 3
Output
[3,3,5,5,6,7]

Explanation: Windows: [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]

Approaches

1. Brute force sliding scan

For each window position, take Math.max of the k elements. Simple but O(n*k).

Time
O(n * k)
Space
O(1)
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 nums values. Front is always the window max. Evict indices outside the window; pop smaller tail indices before adding a new one.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const result = [];
  const deque = []; // stores indices, front = max

  for (let i = 0; i < nums.length; i++) {
    // remove indices outside window
    while (deque.length && deque[0] < i - k + 1) deque.shift();
    // maintain decreasing order: pop smaller tail indices
    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:

Coinbase-specific tips

Coinbase interviewers use this to separate candidates who know data structures from those who have memorised them. The key insight they look for: the deque stores potential future maxima, not just the current max. Framing your explanation around 'we never need a value once a larger one has entered the window' is exactly how Coinbase engineers reason about pruning stale order-book entries.

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

Practice these live with InterviewChamp.AI →