Skip to main content

26. Sliding Window Maximum

hardAsked at Databricks

Return the maximum in every sliding window of size k — a deque-based streaming aggregation Databricks implements in Structured Streaming's watermark-bounded window queries over high-throughput event streams.

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

Problem

Given an integer array nums and a sliding window of size k, return an array of the maximum value in each window position as the window moves left to right.

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: 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 — scan each window

For each window starting position, scan k elements to find the max. O(n*k) — too slow for the 10^5 constraint.

Time
O(n * k)
Space
O(1) auxiliary
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

Maintain a deque of indices in decreasing value order. For each new element, pop from the back while the back is smaller (it can never be the window maximum). Pop from the front when that index falls outside the window. The front is always the current window max.

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

  for (let i = 0; i < nums.length; i++) {
    // remove indices outside the window
    while (deque.length > 0 && deque[0] < i - k + 1) deque.shift();
    // remove smaller elements from the back
    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
    deque.push(i);
    // window is fully formed
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

Tradeoff:

Databricks-specific tips

This is a high-signal hard problem at Databricks because the deque invariant directly models how Photon maintains partial aggregates across streaming micro-batches. Interviewers will probe three things: (1) why you store indices and not values (index needed to expire old elements); (2) why the deque is always decreasing (smaller values can never be future maxima while the larger one is in scope); (3) how this extends to a distributed setting — the answer is a two-pass merge where each partition outputs its local deque state and a coordinator stitches boundary windows. Nail all three to land senior-level.

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

Practice these live with InterviewChamp.AI →