Sliding Minimum - Classic Problems | Repovive

CLS50. Sliding Minimum

2s256 MB

Given an array and a window length $k$ , print the minimum value in every contiguous window of length $k$ from left to right.

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

m_1 \quad m_2 \quad \ldots \quad m_{n-k+1}

Input

6 3
4 2 12 3 -1 6

Explanation

The four windows have minimum values 2, 2, -1, and -1.

Output

2 2 -1 -1

Input

4 1
8 7 6 5

Explanation

With window length 1, each answer is the single value in that window.

Output

8 7 6 5

Input

5 5
3 1 4 1 5

Explanation

There is only one full window, and its minimum value is 1.

Output

Given an array and a window length $k$ , print the minimum value in every contiguous window of length $k$ from left to right.

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

m_1 \quad m_2 \quad \ldots \quad m_{n-k+1}