Skip to main content

23. Sliding Window Maximum

hardAsked at Nubank

Return the maximum in each sliding window of size k as it slides across nums; Nubank uses the monotonic deque to test whether candidates can replace a naive heap with an O(n) trick under real-time risk scoring constraints.

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

Problem

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

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. Max-heap with lazy delete

Push (value, index) into a heap; on each step peek, evicting any top whose index is out of window. O(n log n) and unfriendly to tail-latency SLAs.

Time
O(n log n)
Space
O(n)
// heap of [val, idx]; for each i: push; while top.idx <= i-k pop; if i>=k-1 output top.val.

Tradeoff:

2. Monotonic decreasing deque

Maintain indices in a deque whose values are strictly decreasing. Pop from the back anything smaller than the new value; pop from the front anything outside the window. Front is the max.

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

Tradeoff:

Nubank-specific tips

Nubank engineers grade for the deque insight here — frame it as 'sliding risk-score over the last k card-auth events' and they'll let you skip the heap detour.

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

Practice these live with InterviewChamp.AI →