LeetMotion
Given an integer array nums and an integer k, return the number of good subarrays of nums.
A good subarray is a subarray where the number of different integers in that subarray is exactly k.
For example, [1, 2, 3, 1, 2] has 3 different integers: 1, 2, and 3.
r − l + 1 subarrays.[l..r] contains at most k distinct integers. Every subarray ending at r that starts anywhere from l to r is valid — that's exactly r − l + 1 subarrays: [l..r], [l+1..r], …, [r..r]. Subarrays starting before l would have more than k distinct values. So summing r − l + 1 across all r gives the total count of valid subarrays.atMost call runs in O(n): every element enters the window once (r advances) and leaves at most once (l advances), so total operations ≤ 2n. We call atMost twice — atMost(k) and atMost(k−1) — so the overall complexity is O(n) time and O(k) space for the hash map (at most k+1 distinct keys at any moment before shrinking).Imagine a streaming service analyzing listening sessions. They want to count how many contiguous "listening stretches" contain exactly k different artists. Counting this directly is awkward — but here's a trick: sessions with ≤k artists minus sessions with ≤k−1 artists gives exactly the sessions featuring k distinct artists. Each atMost call sweeps through the session log once, like a producer skimming a tape reel left-to-right — never rewinding more than once per song.
Counting subarrays with exactly k distinct integers directly is tricky. Instead, use the identity:exactly(k) = atMost(k) − atMost(k−1)
atMost(limit) uses a variable sliding window with a frequency map. At each position r, after shrinking to maintain ≤limit distinct, every subarray ending at r starting from l..r is valid — count them all as r − l + 1.
atMost(limit): initialize count={}, l=0, res=0.r: add nums[r] to count. While len(count) > limit: remove nums[l], advance l.r − l + 1 to res (all valid subarrays ending at r).atMost(k) − atMost(k−1) to get the final answer.
Discussion
…