Skip to main content

24. Sliding Window Maximum

hardAsked at LINE

Return the maximum value in every window of size k as it slides across the array — LINE uses this to gauge whether you reach for a monotonic deque, the same primitive behind peak-presence detection.

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

Problem

Given an integer array nums and an integer k, return the maximum value in every contiguous window of size k as it slides from left to right. The output array has length n - k + 1.

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. Recompute each window

For every starting index, scan k elements and record the max.

Time
O(n*k)
Space
O(1)
for(let i=0;i+k<=n;i++){
  let m=-Infinity;
  for(let j=i;j<i+k;j++) m=Math.max(m,nums[j]);
  out.push(m);
}

Tradeoff:

2. Monotonic decreasing deque

Keep a deque of indices whose values are strictly decreasing. For each new index, pop smaller values from the tail, pop the head if it left the window, then the head index is the current window's 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 && 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:

LINE-specific tips

At LINE, frame the sliding max as how you'd track the most active sender per rolling minute window across a chat room — presence + read-receipt framing wins.

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

Practice these live with InterviewChamp.AI →