Sliding Maximum

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
62 upvotes
Asked in companies
Harman InternationalGeeksforGeeksIntuit

Problem statement

You are given an array 'ARR' of integers of length 'N' and a positive integer 'K'. You need to find the maximum elements for each and every contiguous subarray of size K of the array.

For example 
'ARR' =  [3, 4, -1, 1, 5] and 'K' = 3
Output =  [4, 4, 5]

Since the maximum element of the first subarray of length three ([3, 4, -1]) is 4, the maximum element of the second subarray of length three ([4, -1, 1]) is also 4 and the maximum element of the last subarray of length three ([-1, 1, 5]) is 5, so you need to return [4, 4, 5].
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. Then the 'T' test cases follow.

The first line of each test case contains two positive integers 'N' and 'K' which represent the length of the array and length of the subarray respectively.

The Second line of each test case contains 'N' space-separated integers representing the elements of the array.
Output Format : 
For each test case, print 'X' space-separated integer denoting maximum elements for each and every contiguous subarray of size 'K' of the array. Where 'X' is the number of subarray of size 'K' in array 'arr'.

Output for each test case will be printed in a separate line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraint : 
1 <= T <= 10
1 <= N <= 10^5
-10^5 <= arr[i] <= 10^5
1 <= K <= N

Time Limit: 1 sec
Sample Input 1 :
1
5 3
3 2 -6 1 0
Sample Output 1:
3 2 1
Explanation for Input 1:
The subarray of length 'K'      maximum element of the subarray.
3 2 -6                                    3
2 -6 1                                    2
-6 1 0                                    1

Thus, you need to return "3 2 1".
Sample Input 2 :
1
9 3
1 2 3 1 4 5 2 3 6
Sample Output 2:
3 3 4 5 5 5 6
Hint

Think of calculating the maximum element of each subarray of size ‘K’.

Approaches (3)
Brute Force
  1. We know that an array of size ‘N’ will have in total ‘N’ - ‘K’ - 1 subarray of size ‘K'.
  2. Thus, what a trivial solution suggests is that we traverse over all subarrays of size ‘K', and calculate the maximum element in each of these subarrays individually.
  3. So, we can run two nested loops, the outer one will iterate over the starting index of the subarray, and the inner loop will be used to calculate the maximum element in the current subarray of size ‘K’.
Time Complexity

O(N * K), where ‘N’ is the length of the array and ‘K’ is the size of the subarray. 

 

As we are calculating the maximum element of all the subarray of size ‘K’ and there are ‘N’ elements in the array. Hence the overall complexity will be O(N).

Space Complexity

O(1).

 

Constant extra space is used.

Code Solution
(100% EXP penalty)
Sliding Maximum
Full screen
Console