Java Program to Sliding window max using deque with Explanation
Java
Medium
Collections
25 views
2 min read
210 words
This problem helps you practice core Java fundamentals in a practical way. It builds intuition around sliding window, window, size. Let’s break it down step by step so you can implement it confidently.
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)
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)
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.
Step-by-Step Logic
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
Code Solution
This explanation is written for learning purposes and to help beginners understand the concept clearly.
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;}
Output Example
Input:
8
1 3 -1 -3 5 3 6 7
3
Output:
[3, 3, 5, 5, 6, 7]
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
Solution Guide
Problem
Task: for each window of size k, return max. Use deque of indices.
Input / Output
Input
An integer n (size of array)
Then n integers (array elements)
An integer k (window size)
Output
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)
Examples
Input:
8
1 3 -1 -3 5 3 6 7
3
Output:
[3, 3, 5, 5, 6, 7]
Explanation
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.
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
Details
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
Official Solution
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;}
Solutions (0)
No solutions submitted yet. Be the first!
