Sliding window max using deque
Medium
Java
Collections
24 views
Problem Statement
Task: for each window of size k, return max. Use deque of indices.
Input Format
An integer n (size of array)
Then n integers (array elements)
An integer k (window size)
Then n integers (array elements)
An integer k (window size)
Output Format
An array/list containing the maximum of each window of size k.
Example
8 1 3 -1 -3 5 3 6 7 3
[3, 3, 5, 5, 6, 7]
Constraints
• n ≥ 1
• 1 ≤ k ≤ n
• Use Deque of indices
• Time complexity O(n)
• 1 ≤ k ≤ n
• Use Deque of indices
• Time complexity O(n)
Concept Explanation
For every window of size k, we need the maximum element.
We keep a deque of indices where values are in decreasing order.
The front of the deque always holds the index of the current window’s maximum.
We keep a deque of indices where values are in decreasing order.
The front of the deque always holds the index of the current window’s maximum.
Step-by-Step Explanation
1.Read n, the array, and k.
2.Create an empty Deque (store indices).
3.Create an empty result list.
4.Loop index i from 0 to n-1:
• Remove indices from front if they are outside the window
(index
2.Create an empty Deque (store indices).
3.Create an empty result list.
4.Loop index i from 0 to n-1:
• Remove indices from front if they are outside the window
(index
Concept Explanation
For every window of size k, we need the maximum element.
We keep a deque of indices where values are in decreasing order.
The front of the deque always holds the index of the current window’s maximum.
We keep a deque of indices where values are in decreasing order.
The front of the deque always holds the index of the current window’s maximum.
Step-by-Step Explanation
1.Read n, the array, and k.
2.Create an empty Deque (store indices).
3.Create an empty result list.
4.Loop index i from 0 to n-1:
• Remove indices from front if they are outside the window
(index
2.Create an empty Deque (store indices).
3.Create an empty result list.
4.Loop index i from 0 to n-1:
• Remove indices from front if they are outside the window
(index
Input / Output Format
Input Format
An integer n (size of array)
Then n integers (array elements)
An integer k (window size)
Then n integers (array elements)
An integer k (window size)
Output Format
An array/list containing the maximum of each window of size k.
Constraints
• n ≥ 1
• 1 ≤ k ≤ n
• Use Deque of indices
• Time complexity O(n)
• 1 ≤ k ≤ n
• Use Deque of indices
• Time complexity O(n)
Examples
Input:
8
1 3 -1 -3 5 3 6 7
3
Output:
[3, 3, 5, 5, 6, 7]
Example Solution (Public)
static int[] slidingMax(int[] a,int k){if(k<=0||a.length==0) return new int[0];int n=a.length;int[] res=new int[Math.max(0,n-k+1)];java.util.ArrayDeque<Integer> dq=new java.util.ArrayDeque<>();for(int i=0;i<n;i++){while(!dq.isEmpty() && dq.peekFirst()<=i-k) dq.removeFirst();while(!dq.isEmpty() && a[dq.peekLast()]<=a[i]) dq.removeLast();dq.addLast(i);if(i>=k-1) res[i-k+1]=a[dq.peekFirst()];}return res;}
Official Solution Code
static int[] slidingMax(int[] a,int k){if(k<=0||a.length==0) return new int[0];int n=a.length;int[] res=new int[Math.max(0,n-k+1)];java.util.ArrayDeque<Integer> dq=new java.util.ArrayDeque<>();for(int i=0;i<n;i++){while(!dq.isEmpty() && dq.peekFirst()<=i-k) dq.removeFirst();while(!dq.isEmpty() && a[dq.peekLast()]<=a[i]) dq.removeLast();dq.addLast(i);if(i>=k-1) res[i-k+1]=a[dq.peekFirst()];}return res;}
Please login to submit solutions.