Maximum In Sliding Windows Of Size K

Posted: 13 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.

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.
Approach 1

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.
Try Problem