Kth Smallest in Subarray 🍒
MediumAsked in:Amazon•Stage:Online Assessment
arraysliding_windowheap
Problem Statement
Given an array of n integers, a window size m, and an integer k, for every contiguous subarray of length m you must determine the k‑th smallest element. Return the sequence of these k‑th smallest values in the order the windows appear.
Input Format
The first line contains three space‑separated integers n, m, k. The second line contains n space‑separated integers representing the array elements.
Output Format
Print n‑m+1 space‑separated integers, where the i‑th integer is the k‑th smallest element of the subarray arr[i…i+m‑1].
Constraints
- 1 <= n <= 10^5
- 1 <= m <= n
- 1 <= k <= m
- -10^9 <= array elements <= 10^9