24. Sliding Window Maximum
hardAsked at LINEReturn 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 Sam K., 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^41 <= k <= nums.length
Examples
Example 1
nums = [1,3,-1,-3,5,3,6,7], k = 3[3,3,5,5,6,7]Example 2
nums = [1], k = 1[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.