Skip to main content

23. Sliding Window Maximum

hardAsked at Flipkart

Return the max of every length-k window in O(n) — Flipkart uses it to test deque fluency, the trick behind their per-pincode peak-traffic dashboards during sale spikes.

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

Problem

You are given an array nums and a window size k. Return an array of the maximum value in each contiguous window of size k as it slides from left to right.

Constraints

  • 1 <= k <= nums.length <= 10^5
  • -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]

Example 2

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

Approaches

1. Recompute per window

For each window scan all k elements for max.

Time
O(n*k)
Space
O(1)
for (let i = 0; i <= n - k; i++) out.push(Math.max(...nums.slice(i, i + k)));

Tradeoff:

2. Monotonic decreasing deque

Hold indices in a deque with values strictly decreasing front-to-back. Pop the back while it is smaller than the new value and pop the front when it exits the window. Front is always the current max.

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

Tradeoff:

Flipkart-specific tips

Flipkart screeners expect a clean deque-of-indices implementation and a quick note on why heap-based variants run O(n log k) — they have benchmarked both on real traffic streams.

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

Practice these live with InterviewChamp.AI →