Common Trick for Counting Distinct Integers | O(n) Sliding Window Solution
When I saw this problem, I immediately thought of this trick I had seen for counting the number of distinct integers in a subarray. The StackOverflow post does 
When I saw this problem, I immediately thought of this trick I had seen for [counting the number of distinct integers in a subarray](https://stackoverflow.com/a/53066384/3740708). The StackOverflow post does not explain the trick that well, but the trick that they use is, if the subarray ends at index M, then create an array `arr` where `arr[i] = 1` if `i` is the last index <= M in `nums` where `nums[i]` appears, and `arr[i] = 0` otherwise. Then, for any `0 <= j <= M`, the sum of the suffix of `arr` starting from index `j` is the number of distinct elements in the subarray from `j` to `M`. (The StackOverflow post also mentions segment trees, but you don\'t need segment trees for this problem, you just need to know this trick.)\n\nFor me, prefix sums are easier to think about than suffix sums, so I flipped the trick around: If the subarray begins at L, then I created an array `arr` where `arr[i] = 1` if `i` is the *first* index >= L in `nums` where `nums[i]` appears and `arr[i] = 0` otherwise. Then, for any `L <= j < len(nums)`, the sum of the prefix of `arr` ending at index `j` is the number of distinct elements in the subarray from `L` to `j`.\n\nNow, we want to count the number of subarrays which have exactly `K` distinct elements. The way we will approach this problem is, for any `0 <= L < len(nums)`, we want to count the number of distinct subarrays that begin at index `L` which have exactly `K` distinct elements. Let\'s say `arr` is set up as we defined it above. Then, for any `n`, let `f(n)` be the least index `j` of `arr` such that the sum of the prefix of `arr` ending at index `j` is `n`, or `len(nums)` if the sum of all of `arr` is < n. We will maintain two indexes: `lo`, which is `f(K)` and `hi`, which is `f(K+1)`. Then, for any index `lo <= j < hi`, the prefix sum of `arr` ending at `j` is exactly `K`, which means that the subarray from `L` to `j` has exactly `K` distinct elements. Therefore, the number of distinct subarrays that begin at index `L` which have exactly `K` distinct elements is `hi - lo`, so we just add `hi - lo` to our answer.\n\nFinally, how do we maintain the array `arr` as we increase `L` by 1 in our for loop from `L = 0` to `L < len(nums)`? Theoretically we should set `arr[L] = 0` but once we increase `L`, none of the elements with index <= L matter anymore, so we don\'t need to worry about updating `arr[L]`. However, once we increase `L`, `L` is no longer the first index where  `arr[L]` appears anymore anymore, since we are no longer considering elements of index <= L. Therefore, we create an array `next` where `next[i]` is the index of the next occurrence of `nums[i]` in `nums` that happens after index `i` (or -1 if `i` is the last occurrence of `nums[i]` in `nums`). Then, when increasing L, we set `arr[next[L]] = 1`, since `next[L]` is the new first index where `nums[L]` appears. Finally, we update `lo` and `hi` appropriately, increasing the indices until the prefix sums ending at `lo` and `hi` are `K` and `K+1` again, respectively.\n\n```\n# Return the least index j > idx such that arr[j] = 1,\n# or return len(arr) if no such index exists\ndef find_next_one(arr: List[int], idx: int) -> int:\n    N = len(arr)\n    while idx < N:\n        idx += 1\n        if idx == N or arr[idx] == 1:\n            return idx\n    return idx\n\nclass Solution:\n    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n        N = len(nums)\n        # nxt[i] = least j > i such that nums[j] = nums[i], or -1 if i is the last occurrence of nums[i] in nums\n        nxt = [-1 for _ in range(N)]\n        # last_seen[n] = last index where n was seen in nums, or -1 if n hasn\'t been seen before\n        last_seen = [-1 for _ in range(N+1)]\n        # arr[i] = 1 if i is the least index >= L where nums[i] appears in nums\n        # Initially, L = 0\n        arr = [0 for _ in range(N)]\n        for i in range(N):\n            if last_seen[nums[i]] != -1:\n                # Update nxt, if possible\n                nxt[last_seen[nums[i]]] = i\n            else:\n                # i is the first occurrence of nums[i] in nums, so update arr\n                arr[i] = 1\n            # We just saw nums[i], so update last_seen\n            last_seen[nums[i]] = i\n        \n        # lo = least index such that sum from i=0 to lo of arr[i] = K, or N if no such index exists\n        lo = -1\n        pfx = 0\n        while pfx < k:\n            lo += 1\n            if lo == N:\n                break\n            pfx += arr[lo]\n        \n        # hi = least index such that sum from i=0 to lo of arr[i] = K+1, or N if no such index exists\n        # In other words, hi is the position of the next 1 in arr after lo\n        hi = find_next_one(arr, lo)\n        \n        answer = 0\n        for L in range(N):\n            # Remember: Number of subarrays beginning at L with K distinct elements is hi-lo\n            answer += hi-lo\n            \n            # Since we are going to increase L, theoreitcally, we set arr[L] = 0\n            # This means prefix sums at lo and hi just decreased by 1,\n            # so we need to update lo and hi\n            need_to_update_lo = True\n            need_to_update_hi = True\n            if nxt[L] != -1:\n                # Update arr, if possible\n                arr[nxt[L]] = 1\n                # If nxt[L] <= lo, then setting arr[nxt[L]] to 1 cancels out\n                # setting arr[L] to 0, so the prefix sum at lo is still K\n                # and we don\'t need to update lo\n                # Therefore, we only need to update lo if nxt[L] > lo\n                need_to_update_lo = nxt[L] > lo\n                # Same for hi\n                need_to_update_hi = nxt[L] > hi\n                    \n            # If we need to update lo, it\'s because setting arr[L] to 0\n            # decreased the prefix sum of arr at lo by 1,\n            # so to update lo, we just need to find the next 1 in arr that comes after lo\n            if need_to_update_lo:\n                lo = find_next_one(arr, lo)\n            # Same for hi\n            if need_to_update_hi:\n                hi = find_next_one(arr, hi)\n                \n        return answer\n```
['Sliding Window']