Solved Problem - Sliding Window Maximum

Problem Statement

Given an array $A$, of $N$ integers. Print the maximum integer in that subarray for all subarrays of length $K$.

Input format

The first line contains two space-separated integers $N$ and $K$ $(1 \leq K \leq N \leq 10^5)$. The second line contains $N$ space separated integers representing the array $A[]$ $(1 \leq A[i] \leq 10^5).$

Output format

Print a single line containing $N-K+1$ integers—the maximum integer in each subarray of size $K$ from left to right.

---

Sample

Input

6 3
3 8 4 5 1 9

Output

8 8 5 9

---

Brute force

The brute force solution would simply use 2 for-loops. The first loop will determine the endpoint of the $K$-sized subarray. Second loop to iterate through that subarray to find the maximum integer.

See the below code for a better understanding.