Maximum in Subarrays of length K

Easy

0/40

Average time to solve is 27m

Contributed by

7 upvotes

Asked in companies

Problem statement

Given an array of integers of size N and a number K, print the maximum value of each subarray of length K in the array

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains two single space separated integers, N and K.

The second line contains N single space separated integers denoting the elements of the array.

Output format:

A single line consisting of N - K + 1 single space separated integers denoting the maximum values of the K-sized subarrays where the subarrays are taken in a left to right fashion starting from the 0th index.

Constraints:

0 <= N <= 5 * (10 ^ 5)
1 <= K <= N

Time Limit: 1 sec

Sample Input 1:

6 3
10 5 2 7 8 7

Sample Output 1:

10 7 8 8

Explanation for Sample Input 1:

We get the values 10 7 8 8 because:
10 = max(10, 5, 2)
7 = max(5, 2, 7)
8 = max(2, 7, 8)
8 = max(7, 8, 7)

Sample Input 2:

7 3 
12 1 78 90 57 89 56

Sample Output 2:

78 90 90 90 89

Hint 1

Hint 2

Is there a way to just check all k-subarrays one by one and find the maximum element for each?

Approaches (2)

Approach 1

Approach 2

Brute Force Approach

Create a nested loop. The outer loop will go from i = 0 to i = ‘N’ - ‘K’. This will cover the starting indices of all K-subarrays
The inner loop will go from j = i to j = i + K - 1. This will cover all the elements of the K-subarray starting from index i
Keep track of the maximum element in the inner loop and print it.

Time Complexity

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

Space Complexity

O(1) because the extra space being used (looping variables, maximum element) is constant for any N and K

(100% EXP penalty)

Maximum in Subarrays of length K

Console