If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.
In this post, we will see about Sliding Window Maximum in java
Problem
Given an Array of integers and an Integer k, Find the maximum element of from all the contiguous subarrays of size K.
For eg :
int k = 3
output : 6,6,4,4,4,5
for every subarray of size k, Print its maximum element.
Solution
Naive Approach :
The basic solution would be just generating all the contiguous subarrays of size k and looping over them for finding out the max in that current subarray.
Considering, for every spot we are basically taking next ‘k’ element and then we loop over those k elements, so the worst time complexity of this algorithm would be O(n*k).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
package Arrays; import java.util.Scanner; public class slidingWindowMax { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int [] arr = new int[scn.nextInt()]; for(int i = 0; i < arr.length; i++) { arr[i] = scn.nextInt(); } int windowSize = scn.nextInt(); solve(arr, windowSize); } public static void solve(int[] arr, int k) { // starting the outer loop from k and running it until, // current pointer is EQUAL to arr.length for(int i = k; i <= arr.length; i++) { int max = Integer.MIN_VALUE; // this loop considers subarrays of size k ending at i-1 for(int j = i-k; j<i; j++) { max = Math.max(max, arr[j]); } System.out.println(max); } } } |
Slightly Efficient Approach:
We can surely reduce the time taken in finding max for every subarray by using Segment tree.
We can Implement a segment tree for the given array, and we can get the max of every subarray with range query [i, i+k-1].
- Total number of nodes in segment tree :
The worst time complexity for constructing the segment tree would be O(n) because we know,
(i) Leaf nodes of segment tree contains all the elements of the array.
(ii) The number of nodes on last level is the number of nodes on all the upper levels.
- Mathematically,
- Consider length of the array to be n, therefore, leaf nodes of the segment tree will be n.
- hence, the number of nodes on all the upper levels will be n-1.
- Total nodes on segment tree for an array of length n will be:
Tn = leaf nodes + nodes on upper levels
= n + n-1
= 2n+1
- Complexity Analysis
The construction of our segment tree involves calculation for every node only once, so worst time complexity of construction of segment tree will be O(2n+1) i.e O(n).
and result for range query of each subarray will be calculate in O(logk).
The query calculation will be done for all the ‘n-k+1’ subarrays of size k.
therefore overall time complexity for this algorithm will be O((n-k+1)*logk) i.e. O(nlogk).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
package Arrays; import java.util.Scanner; public class slidingWindowMax { static int[] sarr; public static void main(String[] args) { Scanner scn = new Scanner(System.in); int[] arr = new int[scn.nextInt()]; for (int i = 0; i < arr.length; i++) { arr[i] = scn.nextInt(); } int windowSize = scn.nextInt(); int height = (int)Math.ceil((Math.log(arr.length) / Math.log(2))); /* size of segment array i.e. the number of nodes will be = [(2^height+1)-1] */ sarr = new int[1<<height -1]; construct(0, 0, arr.length-1, arr); solve(arr, windowSize); } public static void solve(int[] arr, int k) { for (int i = 0; i <= arr.length - k; i++) { /* finding the result for range query from i to i+k which is basically a subarray. * */ System.out.println(query(0, i, i + k - 1, 0, arr.length - 1)); } } public static int construct(int idx, int start, int end, int[] arr) { /* leaf nodes contains the array elements */ if (start == end) { sarr[idx] = arr[end]; return sarr[idx]; } int mid = (start + end) / 2; /* dividing the range for every node in segment tree into two halves */ int left = construct(2 * idx + 1, start, mid, arr); int right = construct(2 * idx + 2, mid + 1, end, arr); /* result for current index in segment tree will be calculated * in post order, and will be maximum of its two childs. */ sarr[idx] = Math.max(left, right); return sarr[idx]; } public static int query(int idx, int queryStart, int QueryEnd, int start, int end) { /* if our range is completely outside the query, * we need to return a result such that it causes no effect in our final answer. */ if (start > QueryEnd || end < queryStart) { return Integer.MIN_VALUE; } /* if the range of the current segment falls completely * inside the query then return its value. */ else if (start >= queryStart && end <= QueryEnd) { return sarr[idx]; } else { int mid = (start + end) / 2; int left = query(2 * idx + 1, queryStart, QueryEnd, start, mid); int right = query(2 * idx + 2, queryStart, QueryEnd, mid + 1, end); return Math.max(left, right); } } } |
Most Efficient Approach :
In this approach we use Deque which helps us finding the sliding window maximum in O(n).
- A Deque is basically a queue which is open on both the ends for both enqueue and Deque, that is, you can add or remove element either from front or rear.
What we actually do to solve the problem is:
we keep the k elements of the subarrays in the reverse sorted order, We need not keep all the k elements though which we will see later in code.
- Generate the Deque for the first k elements, keeping them sorted in reverse order so that the maximum element is at the front.
- If the Deque is empty, add the element straightaway, else check if the incoming element is greater than the last element, if it is, keep popping the elements from last until the last element of the remaining Deque is greater than the incoming element.
- We also need to remove the elements which belong to different subarray. i.e the indices in the Deque must be in the range, [i, i+k].
An element will only be removed on two conditions :
(i) If the upcoming element is greater than the element at rear, if it, it will keep on popping the element until there comes a larger element at rear of remaining dequeue because we need to keep the array sorted in the reverse order.
(ii) If the element belongs to any other subarray then there is no point in keeping it.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
package org.arpit.java2blog; import java.util.LinkedList; import java.util.Scanner; public class SlidingWindowMax { static int[] sarr; public static void main(String[] args) { Scanner scn = new Scanner(System.in); int[] arr = new int[scn.nextInt()]; for (int i = 0; i < arr.length; i++) { arr[i] = scn.nextInt(); } System.out.print("arr[]: {"); for (int i = 0; i < arr.length; i++) { System.out.print(" "+arr[i]); } System.out.println(" }"); int windowSize = scn.nextInt(); solveEfficient(arr, windowSize); } public static void solveEfficient(int[] arr, int k) { LinkedList<Integer> deque = new LinkedList<>(); for (int i = 0; i < arr.length; i++) { /* keep removing the elements from deque * which are smaller than the current element, * because we need to keep our deque sorted in dec order */ while (!deque.isEmpty() && arr[deque.getLast()] <= arr[i]) { deque.removeLast(); } /* removing the i-k element, because that element does not belong * to the subarray we are currently working on. */ while (!deque.isEmpty() && deque.getFirst() <= i - k) { deque.removeFirst(); } deque.addLast(i); if(i >= k-1) { /* only print when we have processed atleast k elements * to make the very first subarray */ System.out.print(" "+arr[deque.getFirst()]); } } } } |
When you run above program, you will get below output:
2 6 -1 2 4 1 -6 5
arr[]: { 2 6 -1 2 4 1 -6 5 }
3
6 6 4 4 4 5
That’s all about Sliding Window Maximum in java.
