Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 992 with 12 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 992 # by problem number
lcpy gen -s subarrays_with_k_different_integers # by problem name
nums and an integer k, return the number of good subarrays of nums.
A good array is an array where the number of different integers in that array is exactly k.
[1,2,3,1,2] has 3 different integers: 1, 2, and 3.Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
Input: nums = [1,2,1,3,4], k = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].
1 <= nums.length <= 2 * 10^41 <= nums[i], k <= nums.lengthclass Solution:
# Time: O(n)
# Space: O(n)
def subarrays_with_k_distinct(self, nums: list[int], k: int) -> int:
def at_most(target: int) -> int:
if target < 0:
return 0
count: dict[int, int] = {}
left = 0
total = 0
for right, num in enumerate(nums):
count[num] = count.get(num, 0) + 1
while len(count) > target:
count[nums[left]] -= 1
if count[nums[left]] == 0:
del count[nums[left]]
left += 1
total += right - left + 1
return total
return at_most(k) - at_most(k - 1)
| Time | Space |
|---|---|
| O(n) | O(n) |