Shortest Subarray Meeting Minimum Counts for Required Values
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an integer array `nums` and a list of requirements, each a pair `[value, min_count]`. Find the shortest contiguous subarray of `nums` in which every required `value` appears at least `min_count` times. Values that are not mentioned in the requirements may appear in the subarray any number of times.
### Function Signature
```python
def shortest_window_with_counts(nums: list[int], requirements: list[list[int]]) -> list[int]:
```
### Rules
- Return `[left, right]`, the 0-based inclusive bounds of the subarray `nums[left..right]`.
- If several subarrays have the shortest length, return the one with the smallest `left`.
- If no subarray satisfies every requirement, return `[-1, -1]`.
- The `value` entries in `requirements` are distinct.
### Constraints
- `1 <= len(nums) <= 10^5`
- `1 <= len(requirements) <= 10^5`
- `-10^9 <= nums[i] <= 10^9` and `-10^9 <= value <= 10^9`
- `1 <= min_count <= 10^5`
### Examples
**Example 1**
```text
Input: nums = [4, 9, 4, 7, 9, 9, 4, 1], requirements = [[9, 2], [4, 1]]
Output: [4, 6]
```
The subarray `nums[4..6] = [9, 9, 4]` holds two 9s and one 4. A valid subarray needs at least three elements, and no other subarray of length 3 qualifies: `[4, 9, 4]`, `[9, 4, 7]` and `[4, 7, 9]` hold one 9, `[7, 9, 9]` holds no 4, and `[9, 4, 1]` holds one 9.
**Example 2**
```text
Input: nums = [2, 1, 2, 3, 2, 1, 2], requirements = [[2, 2], [1, 1]]
Output: [0, 2]
```
Both `nums[0..2]` and `nums[4..6]` equal `[2, 1, 2]` and have the shortest possible length 3; the one with the smaller left bound is returned.
**Example 3**
```text
Input: nums = [3, 3, 8], requirements = [[3, 2], [5, 1]]
Output: [-1, -1]
```
The value 5 never appears, so no subarray qualifies.
Overview: A coding question asking for the shortest contiguous subarray in which each required value appears at least a given number of times, returning its bounds with a leftmost tie rule or a sentinel when impossible. It tests frequency bookkeeping over subarrays and careful boundary handling.
Read the full Oracle Software Engineer interview experience this question came from
You are given an integer array `nums` and a list `requirements`, where each requirement is a pair `[value, min_count]`. Find the shortest contiguous subarray of `nums` in which every required `value` appears at least `min_count` times. Values that are not mentioned in `requirements` may appear in the subarray any number of times.
Return `[left, right]`, the 0-based inclusive bounds of the subarray `nums[left..right]`.
- If several subarrays have the shortest length, return the one with the smallest `left`.
- If no subarray satisfies every requirement, return `[-1, -1]`.
- The `value` entries in `requirements` are distinct.
### Example 1
```text
Input: nums = [4, 9, 4, 7, 9, 9, 4, 1], requirements = [[9, 2], [4, 1]]
Output: [4, 6]
```
The subarray `nums[4..6] = [9, 9, 4]` holds two 9s and one 4. A valid subarray needs at least three elements, and no other subarray of length 3 qualifies: `[4, 9, 4]`, `[9, 4, 7]` and `[4, 7, 9]` hold one 9, `[7, 9, 9]` holds no 4, and `[9, 4, 1]` holds one 9.
### Example 2
```text
Input: nums = [2, 1, 2, 3, 2, 1, 2], requirements = [[2, 2], [1, 1]]
Output: [0, 2]
```
Both `nums[0..2]` and `nums[4..6]` equal `[2, 1, 2]` and have the shortest possible length 3; the one with the smaller left bound is returned.
### Constraints
- `1 <= len(nums) <= 10^5`
- `1 <= len(requirements) <= 10^5`
- `-10^9 <= nums[i] <= 10^9` and `-10^9 <= value <= 10^9`
- `1 <= min_count <= 10^5`
- The `value` entries in `requirements` are distinct.
- Every input value and every returned index fits in a signed 32-bit integer (no value exceeds 2^31 - 1).
Constraints
- 1 <= len(nums) <= 10^5
- 1 <= len(requirements) <= 10^5
- -10^9 <= nums[i] <= 10^9 and -10^9 <= value <= 10^9
- 1 <= min_count <= 10^5
- The value entries in requirements are distinct.
- Every input value and every returned index fits in a signed 32-bit integer (no value exceeds 2^31 - 1).
Examples
Input: ([4, 9, 4, 7, 9, 9, 4, 1], [[9, 2], [4, 1]])
Expected Output: [4, 6]
Explanation: Source example 1: the earlier valid window nums[0..4] (length 5) must be replaced by the later, shorter nums[4..6] = [9, 9, 4].
Input: ([2, 1, 2, 3, 2, 1, 2], [[2, 2], [1, 1]])
Expected Output: [0, 2]
Explanation: Source example 2: nums[0..2] and nums[4..6] tie at the shortest length 3; the smaller left bound wins.
Hints
- Elements whose value is not listed in requirements never affect whether a subarray qualifies; only the counts of the required values matter.
- Rather than re-checking every requirement for each candidate subarray, keep track of how many requirements are currently met as the subarray changes.
- When two shortest subarrays tie, the one with the smaller left bound must be returned, so a later subarray of the same length must never replace an earlier one.