Array Window Maxima — Problem Statement & Solution Guide
Problem Description
You are provided with a linear sequence of integers representing sensor readings over time and a fixed observation window size k. Your task is to compute the peak value observed within each contiguous subsequence of length k as the window traverses the entire array from left to right.
The sliding mechanism starts at the first element and advances by one position at a time until the window covers the last k elements of the array. For every valid window position, identify the maximum integer present in that specific segment. The final result is a sequence of these peak values, maintaining the chronological order of the windows.
Input consists of an array nums of length n and an integer k, where 1 <= k <= n. Output is an array of length n - k + 1, where the i-th element corresponds to the maximum value in the window starting at index i.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Array Window Maxima"
WHY DOES IT MATTER?
Sliding window patterns appear in time‑series analytics, real‑time monitoring, and any scenario where you need aggregate information over a moving interval. Mastering this pattern equips engineers to write scalable code that avoids redundant recomputation.
OPTIMIZATION CHALLENGE
The key insight is monotonicity: by keeping the deque in decreasing order, any element smaller than a newly added one can never become the maximum for the current or any future window, so it can be safely removed immediately.
REAL-WORLD CONNECTION
Think of a security camera that continuously records the last k seconds; the system must always know the highest motion intensity in that window to trigger alerts. The deque acts like a rolling buffer that discards stale low‑intensity frames and keeps only potential peaks.
During an interview, implement the deque logic first for push/pop, then add the window‑boundary check. Write a helper to clean the front before recording the answer; this separation reduces bugs and clarifies intent.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The sliding window maximum problem asks for the maximum element in every contiguous subarray of size k. A naïve solution recomputes the maximum for each window by scanning k elements, leading to O(n·k) time, which becomes prohibitive when n and k approach 10^5 or larger. The optimal paradigm leverages a double‑ended queue (deque) to maintain candidates for the maximum in a monotonic decreasing order; each element is inserted and removed at most once, yielding linear time. This approach exploits the fact that when the window slides forward, elements that fall out of the window can be discarded, and any element smaller than a newly added one can never become a future maximum, allowing us to prune the deque aggressively.
Interview Questions on This Problem
Q1How would you modify the sliding window maximum algorithm to also return the index of each maximum element?
Store pairs (value, index) in the deque instead of just values. When popping from the front, compare the stored index with the current window's left bound; when pushing, remove from the back while the new value is larger. The front of the deque always holds the current maximum and its index.
Q2Can you solve the sliding window maximum problem in O(n) time using a segment tree or sparse table? Explain the trade‑offs.
A segment tree can answer range maximum queries in O(log n) after O(n) build, leading to O(n log n) total for all windows, which is slower than the deque's O(n) but offers dynamic updates. A sparse table provides O(1) queries after O(n log n) preprocessing, giving O(n log n) overall; it is static and uses more space, whereas the deque is both faster and memory‑efficient for the classic static case.
Q3Why does the monotonic deque guarantee that each array element is processed at most twice?
Each element is pushed to the back exactly once. It may later be popped from the back if a larger element arrives, or from the front when it exits the window. No element is ever re‑inserted, so the total number of push and pop operations is bounded by 2n, ensuring O(n) time.
Examples
Input
nums = [14, 22, 10, 35, 8, 29, 11], k = 3
Output
[22, 35, 35, 29, 29]
Explanation: Window 1: [14, 22, 10] -> max is 22. Window 2: [22, 10, 35] -> max is 35. Window 3: [10, 35, 8] -> max is 35. Window 4: [35, 8, 29] -> max is 35. Window 5: [8, 29, 11] -> max is 29.
Input
nums = [5, 5, 5, 5], k = 2
Output
[5, 5, 5]
Explanation: Window 1: [5, 5] -> max is 5. Window 2: [5, 5] -> max is 5. Window 3: [5, 5] -> max is 5.
Input
nums = [-10, -2, -7, -15, -3], k = 4
Output
[-2, -3]
Explanation: Window 1: [-10, -2, -7, -15] -> max is -2. Window 2: [-2, -7, -15, -3] -> max is -3.
Input
nums = [42], k = 1
Output
[42]
Explanation: Window 1: [42] -> max is 42.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= k <= nums.length
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Maintain a monotonic decreasing deque of indices, updating it in O(1) amortized per step, so the whole array is processed in linear time.
Brute Force Approach
For each window, scan all k elements to find the maximum, repeating this for every possible starting position.
Verified Code Solutions
function solution(nums, k) { let result = []; let deque = []; for (let i = 0; i < nums.length; i++) { while (deque.length > 0 && deque[0] < i - k + 1) deque.shift(); while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) deque.pop(); deque.push(i); if (i >= k - 1) result.push(nums[deque[0]]); } return result; }class Solution { public: vector<int> solution(vector<int>& nums, int k) { vector<int> result; deque<int> dq; for (int i = 0; i < nums.size(); i++) { while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front(); while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back(); dq.push_back(i); if (i >= k - 1) result.push_back(nums[dq.front()]); } return result; } }import java.util.Deque; import java.util.LinkedList; public class Solution { public int[] solution(int[] nums, int k) { int[] result = new int[nums.length - k + 1]; Deque<Integer> deque = new LinkedList<>(); for (int i = 0; i < nums.length; i++) { while (!deque.isEmpty() && deque.peek() < i - k + 1) deque.poll(); while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast(); deque.offer(i); if (i >= k - 1) result[i - k + 1] = nums[deque.peek()]; } return result; } }def solution(nums, k): result = []; deque = []; for i in range(len(nums)): while deque and deque[0] < i - k + 1: deque.pop(0); while deque and nums[deque[-1]] < nums[i]: deque.pop(); deque.append(i); if i >= k - 1: result.append(nums[deque[0]]); return resultfunction solution(nums, k) { let result = []; let deque = []; for (let i = 0; i < nums.length; i++) { while (deque.length > 0 && deque[0] < i - k + 1) deque.shift(); while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) deque.pop(); deque.push(i); if (i >= k - 1) result.push(nums[deque[0]]); } return result; }Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.