Beach Cleanup Stretch
Medium · sliding window
Volunteers are cleaning a long beach. A scout has walked it from end to end and noted the rubbish she saw, one item after another, in the list items. Each value is the kind of that item, written as a whole number.
The team has a collecting plan, the list quota. Each entry [kind, count] says that the team must pick up at least count items of that kind. Every kind appears at most once in quota.
The team will clean one stretch of the beach: items in a row, with none skipped. A stretch is enough if, for every entry of the plan, it holds at least that many items of that kind. Other kinds may appear too and do not matter.
Return [start, length] for the shortest enough stretch: start is the position of its first item (counting from 0) and length is the number of items it holds. If several are equally short, return the one with the smallest start. If no stretch is enough, return [-1, -1].
Examples
Example 1
Input: items = [3, 1, 2, 3, 3, 1, 2], quota = [[3, 2], [1, 1]]
Output: [3, 3]
Positions 3 to 5 hold 3, 3, 1: two items of kind 3 and one of kind 1. No stretch of two items can hold three needed items.
Example 2
Input: items = [5, 5, 5], quota = [[5, 4]]
Output: [-1, -1]
Only three items of kind 5 exist, so the plan can never be met.
Example 3
Input: items = [9, 2, 9], quota = [[2, 1]]
Output: [1, 1]
Constraints
- 1 <= len(items) <= 10^5
- 0 <= items[i] <= 10^9
- 1 <= len(quota) <= 50
- quota[j] = [kind, count] with 0 <= kind <= 10^9 and 1 <= count <= 10^5
- Each kind appears at most once in quota.