Sliding Window Minimum
MediumPractice library · +20 XPqueuesliding windowmonotonic deque
Given an array of integers A of length N, and an integer K, find the minimum element in each contiguous subarray of length K. Print these K minimums separated by spaces.
Input
The first line contains two integers N and K (1 <= K <= N <= 200000). The second line contains N integers A_1, A_2, ..., A_N (-10^9 <= A_i <= 10^9).
Output
Print N-K+1 integers, the minimums of each window of size K.
Constraints
1 <= K <= N <= 200000, -10^9 <= A_i <= 10^9. Time limit 1s.
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 3 1 3 -1 -3 5
Output
-1 -3 -3
The windows are [1, 3, -1], [3, -1, -3], [-1, -3, 5]. Minimums are -1, -3, -3.
Example 2
Input
7 4 10 5 2 7 8 7 2
Output
2 2 2 2
The windows are [10, 5, 2, 7], [5, 2, 7, 8], [2, 7, 8, 7], [7, 8, 7, 2]. Minimums are 2, 2, 2, 2.
Hints
Similar problems
- Maximum Subarray Sum with Fixed LengthMedium
- Longest Prefix With Maximum FrequencyMedium
- Largest Element in PrefixMedium
- Find Minimums in Sliding WindowsMedium
- Longest Subarray with At Most K Duplicate PairsMedium
- Longest Sorted SubsegmentMedium
More topics: Sliding Window problems, Queue and Deque problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 3 1 3 -1 -3 5
Example 2 input
7 4 10 5 2 7 8 7 2