DiffPush Tier Sliding Window · Hard Problems O(n) · O(n)
A colocation facility logs which tenant (as an integer id) consumed each hourly slot. A billing window is 'mixed' when exactly k distinct tenants appear in it. Finance wants the number of mixed windows. The tally trick: count windows with at most k tenants, subtract windows with at most k-1, and the difference is exactly the mixed set.
Input: An integer array nums of tenant ids and an integer k.
Output: Return the number of contiguous subarrays containing exactly k distinct values.
1 <= nums.length <= 2 * 10^41 <= nums[i] <= nums.length1 <= k <= nums.lengthInput: {"nums":[1,2,1,2,3],"k":2}
Output: 7
Seven windows use exactly the tenant pairs {1,2} or {2,3}.
Input: {"nums":[1,2,1,3,4],"k":3}
Output: 3
Only the windows reaching tenant 4's neighborhood carry three distinct ids.