## Problem statement

Given an array of integers `a`, and an integer `k`, find the maximum for each and every contiguous subarray of size `k`.

Example

``````Input: a[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, k = 3
Output: 3 3 4 5 5 5 6
Explanation:
Maximum of subarray {1, 2, 3} is 3
Maximum of subarray {2, 3, 1} is 3
Maximum of subarray {3, 1, 4} is 4
Maximum of subarray {1, 4, 5} is 5
Maximum of subarray {4, 5, 2} is 5
Maximum of subarray {5, 2, 3} is 5
Maximum of subarray {2, 3, 6} is 6``````

## Solution

### Brute force

A basic brute force algorithm is to iterate over the array, consider every subarray of size `k`, and find the maximum in every subarray.

``````import java.util.Scanner;

public class MaxOfAllSubarraysOfSizeK {
private static int[] maxofAllSubarray_BruteForce(int[] a, int k) {
int n = a.length;
int[] maxOfSubarrays = new int[n - k + 1];
int idx = 0;

for(int i = 0; i <= n-k; i++) {
int maxElement = Integer.MIN_VALUE;
for(int j = i; j < i+k; j++) {
if(maxElement < a[j]) {
maxElement = a[j];
}
}
maxOfSubarrays[idx++] = maxElement;
}

return maxOfSubarrays;
}

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = keyboard.nextInt();
}
int k = keyboard.nextInt();
keyboard.close();

int[] result = maxofAllSubarray_BruteForce(a, k);
for(int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
}
}``````

The time complexity of the brute force algorithm is `O(n*k)`.

### Sliding Window

This problem is a variant of the problem First negative number in every window of size k.

If you closely observe the way we calculate the maximum in each k-sized subarray, you will notice that we’re doing repetitive work in the inner loop. Let’s understand it with an example:

``Input: a[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, k = 3``

For the above example, we first calculate the maximum in the subarray `{1, 2, 3}`, then we move on to the next subarray `{2, 3, 1}` and calculate the maximum. Notice that, there is an overlap in both the subarrays:

``````1 2 3
2 3 1``````

So we’re calculating the maximum in the overlapping part (`2, 3`) twice. We can utilize the sliding window technique to save us from re-calculating the maximum in the overlapping subarray and improve the run-time complexity.

In the sliding window technique, we consider each k-sized subarray as a sliding window. To calculate the maximum in a particular window (`2, 3, 1`), we utilize the calculation done for the previous window (`1, 2, 3`).

Since we want to utilize the calculation from the previous window, we need a way to store the calculation for the previous window. We’ll use a `PriorityQueue` to store the elements of the sliding window in decreasing order (maximum first).

The remaining explanation is same as the previous problem we solved using the same technique: First negative number in every window of size k.

Let’s look at the complete implementation:

``````import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class MaxOfAllSubarraysOfSizeK {
private static int[] maxofAllSubarray(int[] a, int k) {
int n = a.length;
int[] maxOfSubarrays = new int[n-k+1];
int idx = 0;

PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());
int windowStart = 0;
for(int windowEnd = 0; windowEnd < n; windowEnd++) {

if(windowEnd-windowStart+1 == k) { // We've hit the window size. Find the maximum in the current window and Slide the window ahead
int maxElement = q.peek();
maxOfSubarrays[idx++] = maxElement;

if(maxElement == a[windowStart]) { // Discard a[windowStart] since we are sliding the window now. So it is going out of the window.
q.remove();
}

windowStart++; // Slide the window ahead
}
}
return maxOfSubarrays;
}

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = keyboard.nextInt();
}
int k = keyboard.nextInt();
keyboard.close();

int[] result = maxofAllSubarray(a, k);
for(int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
}
}``````