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 maximum sliding window.
Input/Output Specifications
- Input: An array of integers
numsand an integerkwhere1 <= k <= nums.length <= 10^5and-10^4 <= nums[i] <= 10^4 - Output: An array containing the maximum element for each sliding window
Constraints
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
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]
Example 3:
Input: nums = [1,-1], k = 1
Output: [1,-1]
Example 4:
Input: nums = [9,11], k = 2
Output: [11]
Solution Approaches
Approach 1: Deque (Monotonic Queue) - Optimal
Algorithm Explanation:
- Use a deque to store indices of array elements
- The deque maintains elements in decreasing order of their values
- For each window, the front of deque contains the index of maximum element
- Remove elements that are out of current window
- Remove elements smaller than current element from the back
Implementation:
Python:
from collections import deque
def maxSlidingWindow(nums, k):
"""
Find maximum in each sliding window using deque
Time: O(n)
Space: O(k)
"""
if not nums or k == 0:
return []
# Deque stores indices of elements in decreasing order
dq = deque()
result = []
for i in range(len(nums)):
# Remove elements outside current window
while dq and dq[0] <= i - k:
dq.popleft()
# Remove 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 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];
}
Deque<Integer> dq = new ArrayDeque<>();
int[] result = new int[nums.length - k + 1];
int resultIndex = 0;
for (int i = 0; i < nums.length; i++) {
// Remove elements outside current window
while (!dq.isEmpty() && dq.peekFirst() <= i - k) {
dq.pollFirst();
}
// Remove 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[resultIndex++] = nums[dq.peekFirst()];
}
}
return result;
}
}
Go:
func maxSlidingWindow(nums []int, k int) []int {
/**
* Find maximum in each sliding window using deque
* Time: O(n)
* Space: O(k)
*/
if len(nums) == 0 || k == 0 {
return []int{}
}
var dq []int // deque to store indices
var result []int
for i := 0; i < len(nums); i++ {
// Remove elements outside current window
for len(dq) > 0 && dq[0] <= i-k {
dq = dq[1:]
}
// Remove elements smaller than current element
for len(dq) > 0 && nums[dq[len(dq)-1]] <= nums[i] {
dq = dq[:len(dq)-1]
}
// Add current element index
dq = append(dq, i)
// Add maximum to result when window is complete
if i >= k-1 {
result = append(result, nums[dq[0]])
}
}
return result
}
JavaScript:
/**
* Find maximum in each sliding window using deque
* Time: O(n)
* Space: O(k)
*/
function maxSlidingWindow(nums, k) {
if (!nums || nums.length === 0 || k === 0) {
return [];
}
const dq = []; // deque to store indices
const result = [];
for (let i = 0; i < nums.length; i++) {
// Remove elements outside current window
while (dq.length > 0 && dq[0] <= i - k) {
dq.shift();
}
// Remove 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 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];
}
var dq = new LinkedList<int>();
var result = new List<int>();
for (int i = 0; i < nums.Length; i++) {
// Remove elements outside current window
while (dq.Count > 0 && dq.First.Value <= i - k) {
dq.RemoveFirst();
}
// Remove 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.Add(nums[dq.First.Value]);
}
}
return result.ToArray();
}
}
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
Approach 2: Max Heap (Priority Queue)
Algorithm Explanation:
- Use a max heap to store elements with their indices
- For each window, add elements to heap
- Remove elements that are outside current window
- The top of heap is the maximum for current window
Implementation:
Python:
import heapq
def maxSlidingWindow_heap(nums, k):
"""
Find maximum in each sliding window using max heap
Time: O(n log n)
Space: O(n)
"""
if not nums or k == 0:
return []
# Use negative values for max heap simulation
heap = []
result = []
for i in range(len(nums)):
# Add current element to heap
heapq.heappush(heap, (-nums[i], i))
# Remove elements outside current window
while heap and heap[0][1] <= i - k:
heapq.heappop(heap)
# Add maximum to result when window is complete
if i >= k - 1:
result.append(-heap[0][0])
return result
Java:
import java.util.*;
class Solution {
/**
* Find maximum in each sliding window using max heap
* Time: O(n log n)
* Space: O(n)
*/
public int[] maxSlidingWindowHeap(int[] nums, int k) {
if (nums == null || nums.length == 0 || k == 0) {
return new int[0];
}
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
int[] result = new int[nums.length - k + 1];
int resultIndex = 0;
for (int i = 0; i < nums.length; i++) {
// Add current element to heap
heap.offer(new int[]{nums[i], i});
// Remove elements outside current window
while (!heap.isEmpty() && heap.peek()[1] <= i - k) {
heap.poll();
}
// Add maximum to result when window is complete
if (i >= k - 1) {
result[resultIndex++] = heap.peek()[0];
}
}
return result;
}
}
Complexity Analysis:
- Time Complexity: O(n log n) - Heap operations take O(log n) time
- Space Complexity: O(n) - Heap can store all elements
Approach 3: Brute Force
Algorithm Explanation:
- For each position, find maximum in the window of size k
- Use nested loops to scan each window
Implementation:
Python:
def maxSlidingWindow_brute(nums, k):
"""
Find maximum in each sliding window using brute force
Time: O(n * k)
Space: O(1)
"""
if not nums or k == 0:
return []
result = []
for i in range(len(nums) - k + 1):
max_val = max(nums[i:i + k])
result.append(max_val)
return result
Complexity Analysis:
- Time Complexity: O(n * k) - For each window, scan k elements
- Space Complexity: O(1) - Only storing result
Key Insights
- Monotonic Deque: Maintains elements in decreasing order, allowing O(1) access to maximum
- Window Management: Remove elements outside current window efficiently
- Index Tracking: Store indices instead of values to handle window boundaries
- Amortized Complexity: Each element is added and removed at most once
Edge Cases
- Empty Array: Return empty result
- k = 1: Each element is its own maximum
- k = array length: Single window with global maximum
- All Same Elements: All windows have same maximum
- Decreasing Array: First element of each window is maximum
Test Cases
def test_maxSlidingWindow():
# Test case 1
nums1 = [1,3,-1,-3,5,3,6,7]
k1 = 3
assert maxSlidingWindow(nums1, k1) == [3,3,5,5,6,7]
# Test case 2
nums2 = [1]
k2 = 1
assert maxSlidingWindow(nums2, k2) == [1]
# Test case 3
nums3 = [1,-1]
k3 = 1
assert maxSlidingWindow(nums3, k3) == [1,-1]
# Test case 4
nums4 = [9,11]
k4 = 2
assert maxSlidingWindow(nums4, k4) == [11]
# Edge case: decreasing array
nums5 = [7,6,5,4,3,2,1]
k5 = 3
assert maxSlidingWindow(nums5, k5) == [7,6,5,4,3]
print("All tests passed!")
test_maxSlidingWindow()
Follow-up Questions
- Minimum Sliding Window: Find minimum in each sliding window?
- Sliding Window Median: Find median in each sliding window?
- Sliding Window Sum: Find sum in each sliding window?
- Variable Window Size: Handle variable window sizes?
- 2D Sliding Window: Extend to 2D arrays?
Common Mistakes
- Wrong Deque Operations: Using wrong methods for deque operations
- Index Confusion: Mixing up indices and values
- Window Boundary: Incorrect window boundary calculations
- Heap Cleanup: Not removing old elements from heap
- Edge Case Handling: Not handling empty arrays or k=0
Interview Tips
- Start with Brute Force: Show understanding of the problem
- Optimize with Deque: Explain the monotonic deque approach
- Discuss Trade-offs: Compare different approaches
- Handle Edge Cases: Mention empty arrays and boundary conditions
- Code Carefully: Pay attention to deque operations and indices
Concept Explanations
Monotonic Deque: A deque that maintains elements in a specific order (increasing or decreasing). For this problem, we maintain decreasing order to always have the maximum at the front.
Sliding Window Technique: A technique where we maintain a window of fixed size and slide it across the array. The key is to efficiently update the window as it moves.
Amortized Analysis: Although individual operations might be expensive, the average cost per operation is low because each element is processed a constant number of times.
When to Use Deque vs Heap: Use deque when you need to maintain order and remove elements from both ends. Use heap when you need to find maximum/minimum but don’t need to maintain order.