1 2 3 1 4 5 2 3 6
3 [ value of k ]
Sample Output :
3
3
4
5
5
5
6
This Question is Asked By Google Indirectly for Maximum in window or subarray of size k in array of size n, yes it is sliding window problem, as window slides we need to find out the maximum in each window. is it ??
Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: Find a good optimal way to get B[i]
Solution: It Can Solved By Two Ways in This Question Data Structure Plays Important Role
The obvious solution with run time complexity of O(nw) is which is not efficient enough. Every time the window is moved, we have to search for the maximum from w elements in the window. where w is size of window & n is size of array
1st Method(Naive Approach)
Data Structure Used : Array
Algorithm: A.for all i=0 to n-w+1 (we should have at-least w elements in window)
B.for all j=i to i+w (keep incrementing windows size form left to right)
C find maximum inn each window & print it or put in array (Auxiliary)
#include
void printMaxInSlidingWindows(int a[],int n,int w)
{
int max=0;
int i=0,j=0;
for (i = 0; i
}
max=a[j];
}
}
printf( " %d ", max);
}
}
int main()
{
int a[]={1,3,-1,-3,5,3,6,7};
printMaxInSlidingWindows(a,8,3);
}
TC O(nw)
SC O(1)
Run Here http://ideone.com/7o3Ta
2nd Method
Data Structure Used: Queue(More Efficient)
We need a data structure where we can store the candidates for maximum value in the window and discard the element, which are outside the boundary of window. For this, we need a data structure in which we can edit at both the ends, front and back. Deque is a perfect candidate for this problem.
We are trying to find a way in which, we need not search for maximum element among all in the window. We will make sure that the largest element in the window would always appear in the front of the queue.
While traversing the array in forward direction if we find a window where element A[i] > A[j] and i > j, we can surely say that A[j], will not be the maximum element for this and succeeding windows. So there is no need of storing j in the queue and we can discard A[j] forever.
For example, if the current queue has the elements: [4 13 9], and a new element in the window has the element 15. Now, we can empty the queue without considering elements 4, 13, and 9, and insert only element 15 into the queue.
Every time, we move to a new window, we will be getting a new element and leave an old element. We should take care of:
Popping elements outside the window from queue front.
Popping elements that are less than new element from the queue.
Push new element in the queue as per above discussion.
Note:Optimization Done In Done so that we can Find The Maximum of Each Window in O(1)
Here Is Tunning Code
import java.util.*;
class Maximumin_SlidingWindow
{
public static void main(String ar[])
{
Integer a[]=new Integer[]{1,3,-1,-3,5,3,6,7};
int w=3,i=0;
int size=a.length;
Integer b[]=new Integer[size-w+1];
maxSlidingWindow(a,size,w,b);
for(i=0;i
//Initilize deque Q for first window
for (int i = 0; i < w; i++) { while (!Q.isEmpty() && A[i] >= A[Q.peekLast()])
Q.pollLast();
Q.offerLast(i);
}
for (int i = w; i < n; i++) { B[i-w] = A[Q.peekFirst()]; //update Q for new window while (!Q.isEmpty() && A[i] >= A[Q.peekLast()])
Q.pollLast();
//Pop older element outside window from Q
while (!Q.isEmpty() && Q.peekFirst() <= i-w)
Q.pollFirst();
//Insert current element in Q
Q.offerLast(i);
}
B[n-w] = A[Q.peekFirst()];
}
}
TC O(n)n Since Eacj Array Element is Inserted & deleted At-Most Once
SC O(1)
Run Here http://ideone.com/KLIpO
http://ideone.com/TftYg
