Quick 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.

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

  1. Elements whose value is not listed in requirements never affect whether a subarray qualifies; only the counts of the required values matter.
  2. Rather than re-checking every requirement for each candidate subarray, keep track of how many requirements are currently met as the subarray changes.
  3. 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.

Shortest Subarray Meeting Minimum Value Counts

mediumOracleSoftware Engineer

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

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

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).

Examples

Example 1
Input
([4, 9, 4, 7, 9, 9, 4, 1], [[9, 2], [4, 1]])
Output
[4, 6]
Notes
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].
Example 2
Input
([2, 1, 2, 3, 2, 1, 2], [[2, 2], [1, 1]])
Output
[0, 2]
Notes
Source example 2: nums[0..2] and nums[4..6] tie at the shortest length 3; the smaller left bound wins.

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).

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def shortest_window_with_counts(nums: list[int], requirements: list[list[int]]) -> list[int]:
Sample call
shortest_window_with_counts([4, 9, 4, 7, 9, 9, 4, 1], [[9, 2], [4, 1]])
Language
Case 1
Input
([4, 9, 4, 7, 9, 9, 4, 1], [[9, 2], [4, 1]])
Expected
[4, 6]
Case 2
Input
([2, 1, 2, 3, 2, 1, 2], [[2, 2], [1, 1]])
Expected
[0, 2]

Browse More Questions

Show the approach

Approach

Sliding window with two pointers. Map each required value to its min_count. For the current window nums[left..right], keep how many copies of each required value it holds and a counter of how many requirements are currently met. Advance right one step at a time; when a required value's count reaches exactly its min_count, one more requirement is met. While every requirement is met, the window is valid: record it if it is strictly shorter than the best so far, then remove nums[left] and advance left. A requirement stops being met only when its count drops below its min_count, so surplus copies and values not in requirements are shed freely. Invariant: after the inner loop for a given right, left is one past the largest start for which nums[start..right] is valid, so the last window recorded at that step is the shortest valid window ending at right. Correctness: a shortest valid window [l, r] must also be the shortest valid window ending at r (otherwise a shorter valid window would exist), so it is examined when right = r. Windows of equal length are examined in increasing order of right, which is increasing order of left, and the best answer changes only on a strictly shorter length, so among the shortest windows the one with the smallest left is kept. Edge cases: a required value that never appears, a min_count larger than the number of occurrences, or more requirements than elements all keep the counter below the number of requirements, so [-1, -1] is returned; one element meeting one requirement gives [0, 0]. Each index enters and leaves the window at most once, so the scan is linear.

Time complexity:
O(n + m), where n = len(nums) and m = len(requirements)
Space complexity:
O(n + m)