Maximum Of All Subarrays Of Size k.

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

Problem statement

You are given an array consisting of N non-negative integers, and an integer K denoting the length of a subarray, your task is to determine the maximum elements for each subarray of size K.

Note:
A subarray is a contiguous subset of an array.

The array may contain duplicate elements.

The given array follows 0-based indexing.

It is guaranteed that there exists at least one subarray of size K.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of the input contains an integer T denoting the number of test cases. 

The first line of each test case contains two space-separated integers N and K, as described in the problem statement.

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 in a new line, X space-separated integers, where X is the number of possible subarrays of size K, and the ith integer denote the maximum element of the ith possible subarray of size K starting from the left. 
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^5
1 <= K <= N
1 <= arr[i] <= 10^9

Time Limit: 1sec
Sample Input 1:
1
4 2
10 7 8 11
Sample Output 1:
10 8 11
Explanation For Sample Input 1:
The first subarray of length 2 is [10,7] and the maximum of it is 10, then the next subarray of length 2 is [7,8] and the maximum of it is 8, and the last subarray of size 2 is [8,11] and the maximum of it is 11, So the output is [10,8,11].
Sample Input 2:
1
4 3 
11 3 9 6
Sample Output 2:
11 9
Hint

Consider each window of size K one by one.

Approaches (3)
Brute force approach
  • The Idea behind this brute force approach is to consider each subarray of size K by fixing a point i in the array and then consider all the points after it till we have considered K elements from the starting point i and finding the maximum element in it and then storing it.
  • Now, run a loop(say, loop variable i) till (N-K) elements of the array:
    • Run a nested loop(say, loop variable j) through the elements starting from index i up to the next k elements.
    • At each iteration of the inner loop keep a track of the maximum element in that subarray and finally after the nested loop ends store the answer for this subarray and continue the process for next i.
Time Complexity

O(N * K), where N is the number of elements in the array and K is the length of the subarray.

 

The time complexity is O(N * K) because the outer loop will run for the order of O(N) and the inner loop will run for the order of O(K), So the total complexity is O(N * K).

Space Complexity

O(X), where X is the number of possible subarrays of size K.

 

We are storing the maximum of all the subarrays of size K, so the space complexity is O(X).

Code Solution
(100% EXP penalty)
Maximum Of All Subarrays Of Size k.
Full screen
Console