Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 18 Feb, 2021

Maximum Of All Subarrays Of Size k.

Moderate
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.
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

Approaches

01 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.