Maximum In Sliding Windows Of Size K

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
70 upvotes
Asked in companies
AppleWalmartOYO

Problem statement

Given an array/list of integers of length ‘N’, there is a sliding window of size ‘K’ which moves from the beginning of the array, to the very end. You can only see the ‘K’ numbers in a particular window at a time. For each of the 'N'-'K'+1 different windows thus formed, you are supposed to return the maximum element in each of them, from the given array/list.

Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line contains a single integer ‘T’ denoting the number of test cases. The 'T' test cases follow.

The first line of each test case contains two single space-separated integers ‘N’ and ‘K’ denoting the number of elements in the array/list and the size of the window size respectively.

The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.
Output format : 
For each test case, print the output array/list which contains the sliding window maximum in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 50
1 <= N <= 10^4
1 <= K <= N
0 <= ARR[i] <= 10^5

Where, ARR[i] denotes the i-th element in the array/list.

Time Limit: 1 sec.
Sample Input 1 :
2
3 1
1 2 2
5 2
4 2 1 4 4
Sample Output 1 :
1 2 2
4 2 4 4
Explanation to Sample Input 1 :
In the first test case, 
The maximum of window {1} is 1.
The maximum of window {2} is 2.
The maximum of window {2} is 2.
So the output will be {1, 2, 2}.

In the second test case, 
The maximum of window {4,2} is 4.
The maximum of window {2,1} is 2.
The maximum of window {1,4} is 4.
The maximum of window {4,4} is 4.
So the output will be {4, 2, 4, 4}.
Sample Input 2 :
2
5 3
2 2 2 3 3
7 4
2 3 1 4 5 1 5
Sample Output 2 :
2 3 3
4 5 5 5
Explanation to Sample Input 2 :
In the first test case, 
The maximum of window {2,2,2} is 2.
The maximum of window {2,2,3} is 3.
The maximum of window {2,3,3} is 3.
So the output will be {2, 3, 3}.

In the second test case, 
The maximum of window {2,3,1,4} is 4.
The maximum of window {3,1,4,5} is 5.
The maximum of window {1,4,5,1} is 5.
The maximum of window {4,5,1,5} is 5.
So the output will be {4, 5, 5, 5}.
Hint

Keep on moving the sliding window of size ‘K’ from the start of the array/list till the end.

Approaches (3)
Brute Force

Our intuition here is to go through each sliding window and keep track of the maximum element in each sliding window. To implement the same we run two nested loops, where the outer loop which will mark the starting point of the subarray of length k, the inner loop will run from the starting INDEX to INDEX + K, K elements from starting index and store the maximum element among these K elements into the answer.

 

STEPS :

 

  1. Use two nested loops.
  2. The outer loop from starting INDEX = 0 to N - K th elements.
  3. The inner loop will run for ‘K’ iterations for the window size of ‘K’.
  4. Now create a variable to store the maximum of K elements that are traversed in the inner loop.
  5. Find the maximum of K elements traversed by the inner loop.
  6. Store the maximum element in every iteration of the outer loop which is nothing but the sliding window maximum of the current window.
Time Complexity

O(N*K), where N is the number of elements in the given array/list and ‘K’ is the given window size.

 

We are pivoting N-K+1 elements once and for every element, we are traversing the given array/list for K iterations (traversing the window) to find the maximum value. So there will be a total of N-K+1 elements to pivot and then traversing the window of size K in the array/list will take O(K) time. So the overall total time complexity will be O((N-K+1)*K) i.e O(N*K).

Space Complexity

O(N), where N is the number of elements in the given array/list.

 

There is no extra space required in the implementation but we have to consider the space where we are storing the maximum elements of the windows of K length which in the worst case can go up to N elements in the output list/array. So the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Maximum In Sliding Windows Of Size K
Full screen
Console