Count Elements Less Than K in Window
Given an array of N integers and an integer K, find the count of elements that are strictly less than K within every contiguous subarray (window) of size M. Print these counts for all possible windows.
Input
The first line contains three space-separated integers N, M, and K. The second line contains N space-separated integers representing the array elements.
Output
Print N - M + 1 lines, where each line contains the count of elements strictly less than K in the corresponding window of size M.
Constraints
1 <= N <= 1000 1 <= M <= N 1 <= K <= 1000 Elements of the array are between 1 and 1000.
Example 1
5 3 5 1 6 3 4 2
2 2 3
For the first window [1, 6, 3], elements less than 5 are 1 and 3 (count 2). For [6, 3, 4], elements less than 5 are 3 and 4 (count 2). For [3, 4, 2], elements less than 5 are 3, 4, and 2 (count 3).
Example 2
7 4 10 11 12 3 9 8 15 6
2 3 3 3
Windows: [11, 12, 3, 9] (count 2), [12, 3, 9, 8] (count 3), [3, 9, 8, 15] (count 3), [9, 8, 15, 6] (count 3).
Hints
Similar problems
- Count Subarrays with Target SumEasy
- Longest Subarray with Equal HalvesMedium
- Count Subarrays with Distinct ElementsMedium
- Distinct Elements in a Sliding WindowMedium
- Longest Subarray with Distinct ElementsHard
- Longest Substring With At Most K Distinct CharactersMedium
More topics: Hash Map and Hashing problems, Sliding Window problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 3 5 1 6 3 4 2
7 4 10 11 12 3 9 8 15 6