Maximum in Subarrays of length K

Posted: 28 Jul, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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

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
Approach 1
  1. 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
  2. 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
  3. Keep track of the maximum element in the inner loop and print it.
Try Problem