A factory assembly line produces n items in sequence, each stamped with an integer quality rating. A quality inspector wants to examine the shortest possible contiguous run of items -- a batch -- whose combined 'distinct quality total' reaches at least a target value K. The distinct quality total of a batch counts each quality rating that appears in the batch exactly once, no matter how many items in the batch share that rating -- that is, it is the sum of the set of distinct ratings present in the batch, not the sum of all items in the batch.
Determine the minimum number of consecutive items that must be included in a batch so that its distinct quality total is at least K. If no contiguous batch (including the entire line) reaches the target, report -1.
Line 1: two integers n and K. Line 2: n integers q_1, q_2, ..., q_n -- the quality rating of each item, in order along the line.
A single integer: the minimum length of a contiguous batch whose distinct quality total is at least K, or -1 if no such batch exists.
Example 1
Input
5 5 1 2 3 4 5
Expected
1
Explanation
The item with quality rating 5 alone forms a batch of length 1 whose distinct quality total is 5, meeting the target K=5. No shorter batch is possible, so the answer is 1.
Example 2
Input
6 6 4 1 2 4 1 3
Expected
2
Explanation
Consider the batch made of the 3rd and 4th items, with quality ratings 2 and 4. Their distinct quality total is 2+4=6, meeting the target K=6, using only 2 items. No single item has a rating of 6 or more (the ratings present are 1, 2, 3, 4), so a batch of length 1 cannot reach the target, making 2 the minimum length.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →