Problem

Submissions

Hints & solutions

Discuss

Maximum of All Subarrays of Size K

Easy

0/40

Average time to solve is 15m

Contributed by

31 upvotes

Asked in companies

Problem statement

You are given an array “A” of N integers. Your task is to find the maximum element in all K sized contiguous subarrays from left to right.

For Example:

If A = [3, 2, 3], and K = 2.
Then max of [3, 2] = 3 and max of [2, 3] = 3
So, the answer will be [3, 3]

If A = [3, 2, 3, 5, 1, 7] and K = 3.
Then max of [3, 2, 3] = 3 
Then max of [2, 3, 5] = 5 
Then max of [3, 5, 1] = 5 
Then max of [5, 1, 7] = 7 
So  the answer will be [3, 5, 5, 7]

Follow Up :

Can you solve the problem in O(N) time complexity and O(K) space complexity?

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 contains two space-separated integers N and K.

The second line of each test contains N space-separated integers, denoting the elements of array A.

Output format :

For each test case, print a single line containing N -  K + 1 space-separated integers denoting values of the maximum element in K size subarrays.

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 <= A[i] <= 10^9

Time Limit: 1sec

Sample Input 1 :

Sample Output 1 :

2 1 1
1 3

Explanation For Sample Input 1:

For the first test case,the given A = [2, 1, 1]  and K = 1
Therefore, max([2]) = 2 , max([1]) = 1, max([1]) = 1
Hence our answer is [2, 1, 1] 

For the second test case, the given A = [1, 1, 3] and K = 2 
Therefore, max([1, 1]) = 1, max([1, 3]) = 3
Hence our answer is [1, 3].

Sample Input 2 :

Sample Output 2 :

3 3
3 4 5

Hint 1

Hint 2

Hint 3

Hint 4

Think of a solution using brute force.

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Brute force Approach

Steps:

Declare an empty array to store a maximum of all K sized subarrays, say the answer.
Generate all subarrays of size K using two nested loops.
Find max in each of K sized subarrays and add it to the answer.
Finally, Return the answer.

Time Complexity

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

In the worst case, generating all subarrays takes O(N * K) time. Hence the overall complexity will be O(N * K).

Space Complexity

O(1)

Constant extra space is used.

(100% EXP penalty)

Maximum of All Subarrays of Size K

Console