Language Selection
Choose your preferred programming language
Showing: Python
Sliding Window Maximum
Problem Statement
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Examples
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1
Output: [1]
Explanation: Single element window.
Example 3:
Input: nums = [1,-1], k = 1
Output: [1,-1]
Explanation: Each window has one element.
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
Approach 1: Monotonic Deque (Optimal)
Algorithm
Use a deque to maintain elements in decreasing order for efficient maximum finding.
Steps:
- Use a deque to store indices of elements in decreasing order
- For each element:
- Remove indices that are out of current window
- Remove indices of elements smaller than current element
- Add current element index to deque
- Add maximum element to result when window is complete
Implementation
Python:
from collections import deque
def maxSlidingWindow(nums, k):
"""
Find maximum in each sliding window using monotonic deque
Time: O(n)
Space: O(k)
"""
if not nums or k == 0:
return []
result = []
dq = deque() # Store indices
for i in range(len(nums)):
# Remove indices that are out of current window
while dq and dq[0] <= i - k:
dq.popleft()
# Remove indices of elements smaller than current element
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()
# Add current element index
dq.append(i)
# Add maximum to result when window is complete
if i >= k - 1:
result.append(nums[dq[0]])
return result
Java:
import java.util.*;
class Solution {
/**
* Find maximum in each sliding window using monotonic deque
* Time: O(n)
* Space: O(k)
*/
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k == 0) {
return new int[0];
}
int[] result = new int[nums.length - k + 1];
Deque<Integer> dq = new ArrayDeque<>(); // Store indices
for (int i = 0; i < nums.length; i++) {
// Remove indices that are out of current window
while (!dq.isEmpty() && dq.peekFirst() <= i - k) {
dq.pollFirst();
}
// Remove indices of elements smaller than current element
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
dq.pollLast();
}
// Add current element index
dq.offerLast(i);
// Add maximum to result when window is complete
if (i >= k - 1) {
result[i - k + 1] = nums[dq.peekFirst()];
}
}
return result;
}
}
Go:
func maxSlidingWindow(nums []int, k int) []int {
/**
* Find maximum in each sliding window using monotonic deque
* Time: O(n)
* Space: O(k)
*/
if len(nums) == 0 || k == 0 {
return []int{}
}
result := make([]int, len(nums)-k+1)
dq := []int{} // Store indices
for i := 0; i < len(nums); i++ {
// Remove indices that are out of current window
for len(dq) > 0 && dq[0] <= i-k {
dq = dq[1:] // Remove first element
}
// Remove indices of elements smaller than current element
for len(dq) > 0 && nums[dq[len(dq)-1]] <= nums[i] {
dq = dq[:len(dq)-1] // Remove last element
}
// Add current element index
dq = append(dq, i)
// Add maximum to result when window is complete
if i >= k-1 {
result[i-k+1] = nums[dq[0]]
}
}
return result
}
JavaScript:
/**
* Find maximum in each sliding window using monotonic deque
* Time: O(n)
* Space: O(k)
*/
function maxSlidingWindow(nums, k) {
if (!nums || nums.length === 0 || k === 0) {
return [];
}
const result = [];
const dq = []; // Store indices
for (let i = 0; i < nums.length; i++) {
// Remove indices that are out of current window
while (dq.length > 0 && dq[0] <= i - k) {
dq.shift();
}
// Remove indices of elements smaller than current element
while (dq.length > 0 && nums[dq[dq.length - 1]] <= nums[i]) {
dq.pop();
}
// Add current element index
dq.push(i);
// Add maximum to result when window is complete
if (i >= k - 1) {
result.push(nums[dq[0]]);
}
}
return result;
}
C#:
using System.Collections.Generic;
public class Solution {
/// <summary>
/// Find maximum in each sliding window using monotonic deque
/// Time: O(n)
/// Space: O(k)
/// </summary>
public int[] MaxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.Length == 0 || k == 0) {
return new int[0];
}
int[] result = new int[nums.Length - k + 1];
var dq = new LinkedList<int>(); // Store indices
for (int i = 0; i < nums.Length; i++) {
// Remove indices that are out of current window
while (dq.Count > 0 && dq.First.Value <= i - k) {
dq.RemoveFirst();
}
// Remove indices of elements smaller than current element
while (dq.Count > 0 && nums[dq.Last.Value] <= nums[i]) {
dq.RemoveLast();
}
// Add current element index
dq.AddLast(i);
// Add maximum to result when window is complete
if (i >= k - 1) {
result[i - k + 1] = nums[dq.First.Value];
}
}
return result;
}
}
Complexity Analysis
- Time Complexity: O(n) - Each element is added and removed at most once
- Space Complexity: O(k) - Deque stores at most k elements
Key Insights
- Monotonic Deque: Maintain elements in decreasing order
- Index Storage: Store indices instead of values for window boundary checking
- Window Boundary: Remove elements that are out of current window
- Efficient Maximum: Always get maximum from front of deque
- Amortized O(1): Each element is added and removed at most once
Edge Cases
- Empty Array: Handle empty input array
- Single Element: Handle array with single element
- k = 1: Handle window size of 1
- k = n: Handle window size equal to array length
- All Decreasing: Handle arrays where all elements are decreasing
Test Cases
def test_maxSlidingWindow():
# Test case 1: Normal case
nums1 = [1, 3, -1, -3, 5, 3, 6, 7]
k1 = 3
result1 = maxSlidingWindow(nums1, k1)
expected1 = [3, 3, 5, 5, 6, 7]
assert result1 == expected1
# Test case 2: Single element
nums2 = [1]
k2 = 1
result2 = maxSlidingWindow(nums2, k2)
expected2 = [1]
assert result2 == expected2
# Test case 3: Two elements
nums3 = [1, -1]
k3 = 1
result3 = maxSlidingWindow(nums3, k3)
expected3 = [1, -1]
assert result3 == expected3
# Test case 4: All decreasing
nums4 = [7, 6, 5, 4, 3, 2, 1]
k4 = 3
result4 = maxSlidingWindow(nums4, k4)
expected4 = [7, 6, 5, 4, 3]
assert result4 == expected4
print("All tests passed!")
test_maxSlidingWindow()
Follow-up Questions
- Sliding Window Minimum: Find minimum in each sliding window?
- Sliding Window Median: Find median in each sliding window?
- Sliding Window Sum: Find sum in each sliding window?
- Sliding Window with Constraints: Add additional constraints?
- Sliding Window in 2D: Handle 2D sliding windows?
Common Mistakes
- Wrong Deque Order: Not maintaining decreasing order in deque
- Index Confusion: Confusing indices with values
- Window Boundary: Not handling window boundary correctly
- Edge Cases: Not handling empty array or k=0
- Time Complexity: Not optimizing from O(n*k) to O(n)
Interview Tips
- Start with Brute Force: Show understanding of the problem
- Optimize with Deque: Explain monotonic deque approach
- Handle Edge Cases: Mention empty array and k=0 cases
- Discuss Trade-offs: Compare time vs space complexity
- Follow-up Ready: Be prepared for minimum and median variations
Concept Explanations
Sliding Window Maximum: We need to find the maximum element in each window of size k as it slides through the array.
Monotonic Deque: A deque that maintains elements in a specific order (in this case, decreasing order from front to back). This allows us to efficiently find the maximum element.
Index Storage: We store indices instead of values in the deque. This helps us:
- Check if elements are out of the current window
- Access the actual values when needed
- Maintain the order efficiently
Window Boundary: We remove elements from the front of the deque when they are out of the current window (i.e., their index is <= i - k).
Efficient Maximum: The front of the deque always contains the index of the maximum element in the current window, so we can get the maximum in O(1) time.
Why Deque Works: The deque helps us maintain the order of elements and efficiently find the maximum element without having to search through the entire window.
Amortized Analysis: Each element is added to the deque exactly once and removed at most once, so the total time complexity is O(n).
Space Optimization: We use O(k) extra space to achieve O(n) time complexity, which is a good trade-off for this problem.