Dsa
Sliding Window
Medium
The Hybrid Threshold
An analytics engine needs to identify the shortest contiguous subsegment of logs that meets two conditions: the sum of the severity scores must be at least S, and the number of unique event IDs must be at least K.
Input Format:
- The first line contains two integers: K (unique ID threshold) and S (sum threshold).
- The second line contains a space-separated list of integers representing the severity scores. (Note: In this scenario, severity scores and event IDs are the same integer value).
Output Format:
- A single integer representing the length of the shortest subsegment. If no such subsegment exists, print 0.
Example:
Input:
3 15
5 1 5 2 5 8
Output:
4
(Explanation: The subsegment [2, 5, 8] has sum 15 but only 3 unique elements. Wait, the unique IDs are {2, 5, 8}. The length is 3. Let's re-check: [5, 2, 5, 8] is sum 20, unique {5, 2, 8}. The subsegment [1, 5, 2, 5] is sum 13 (too low). The shortest valid one is [2, 5, 8] with length 3.)
Key concepts
sliding_windowhash_map
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now