Sliding Window Maximum
The key idea
Keep a deque of indices whose values are in decreasing order. The front index always holds the window's maximum. Before adding a new index, pop every smaller value off the back (they can never be the max again while the bigger newcomer is in the window), and drop the front if it has slid out of the window.
Problem
You are given an array of integers nums and a window size k. A window of size k slides over the array from the very left to the very right. At each position you can only see the k numbers inside the window, and the window moves one position to the right each time.
Return an array of the maximum value inside the window at every position, in order. A brute-force scan of each window costs O(n*k); the goal is to do it in O(n) total by reusing work across overlapping windows.
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
Examples
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Input: nums = [1], k = 1
Output: [1]
Complexity
Time: O(n) Space: O(k)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Sliding Window problems
- Find All Anagrams in a StringMEDIUM
- Longest Continuous Increasing SubsequenceEASY
- Longest Repeating Character ReplacementMEDIUM
- Longest Subarray of 1's After Deleting One ElementMEDIUM
- Longest Substring Without Repeating CharactersMEDIUM
- Max Consecutive Ones IIIMEDIUM
- Maximum Average Subarray IEASY
- Maximum Number of Vowels in a Substring of Given LengthMEDIUM
- Minimum Size Subarray SumMEDIUM
- Minimum Window SubstringHARD
- Permutation in StringMEDIUM
- Substring with Concatenation of All WordsHARD