992. Subarrays with K Different Integers
https://leetcode.com/problems/subarrays-with-k-different-integers/description/
Given an integer array 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.
- For example,
[1,2,3,1,2]has3different integers:1,2, and3.
A subarray is a contiguous part of an array.
Example 1:
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]
Example 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].
Constraints:
1 <= nums.length <= 2 * 1041 <= nums[i], k <= nums.length
---
Intuition
Combine results from subarrays with atmost k diferent integers
atmost(k) - atmost(k - 1)
track subarrays with atmost k distinct with two pointers, and freq hashmap
simply add element at hi
while (map.size() > k) - strictly greater, because == is allowed
remove, increment lo
ans += number of elements between hi and lo inclusive, hi - lo + 1
---
Time = O(N) - two linear scans
Space = O(K) - hashmap
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int subarraysWithKDistinct(int[] nums, int k) { | |
| return subarraysWithAtMostK(nums, k) - subarraysWithAtMostK(nums, k - 1); | |
| } | |
| private int subarraysWithAtMostK(int[] nums, int k) { | |
| int ans = 0, lo = 0, hi = 0; | |
| // freq of each number | |
| Map<Integer, Integer> map = new HashMap<Integer, Integer>(); | |
| while (hi < nums.length) { | |
| map.put(nums[hi], map.getOrDefault(nums[hi], 0) + 1); | |
| hi++; | |
| // remove only if strictly greater, == is allowed | |
| while (map.size() > k) { | |
| map.put(nums[lo], map.get(nums[lo]) - 1); | |
| if (map.get(nums[lo]) == 0) { | |
| map.remove(nums[lo]); | |
| } | |
| lo++; | |
| } | |
| // number of subarrays between hi, and lo inclusive | |
| ans += (hi - lo + 1); | |
| } | |
| return ans; | |
| } | |
| } |
