Easy python O(n) O(1) solution beats 94% with one array traversal
Intuition\nIt is easy to solve this problem using the sliding window with one array traversal.\n\n# Approach\nTo implement this approach:\n\n1. Maintain a dicti
# Intuition\nIt is easy to solve this problem using the sliding window with one array traversal.\n\n# Approach\nTo implement this approach:\n\n1. Maintain a dictionary, $l$, to count the frequencies of elements in the window. Also, keep track of the index, $i$, of the leftmost element in the window. Additionally, track $c$, the count of elements before the window, such that removing them will yield the same number of unique elements in the window.\n\n2. Traverse through the array with index $j$:\n\n+ Increment $l[nums[j]]$.\n\n+ If the length of $l$ (number of unique elements in the window) exceeds $k$, reset $c$ to 0, because we need to shift $i$ to the right and all elements before the current $i$ won\'t form a contiguous subarray with our future window. While the length of $l$ exceeds $k$, move $i$ to the right by decreasing $l[nums[i]]$ and deleting it if it becomes 0.\n\n+ After this, calculate the count of elements before the window that, upon removal, will maintain the same number of unique elements in our window. Iterate while $l[nums[i]] > 1$ (indicating that removing the $i$th element won\'t reduce the count of unique elements in the window). Move to the right, decreasing $l[nums[i]]$.\n\n+ If $len(l) == k$, increment $ans$ by $c+1$. This accounts for the $c$ elements before the current array that do not affect the length of $l$ (number of unique elements in the window). We can add either an empty array or $c$ contiguous subarrays to the left of the current array to our window.\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(20001)=O(1)$$\n\n# Code\n```\nclass Solution:\n    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n        l = defaultdict(int)\n        ans = 0\n        i = 0\n        c = 0\n        for j in range(len(nums)):\n            l[nums[j]] += 1\n            if len(l) > k:\n                c = 0\n                while len(l) > k:\n                    l[nums[i]] -= 1\n                    if l[nums[i]] == 0:\n                        del l[nums[i]]\n                    i += 1\n            while l[nums[i]] > 1:\n                c += 1\n                l[nums[i]] -= 1\n                i += 1\n            if len(l) == k:\n                ans += c + 1\n        return ans\n```\n\n![image.png](https://assets.leetcode.com/users/images/44895ff0-9fe5-4159-84ae-02226a375dd7_1711803780.4737437.png)\n\n![image.png](https://assets.leetcode.com/users/images/6b31281e-5db2-4fc7-beae-57e52f3ffb65_1711803812.8525023.png)\n
['Array', 'Hash Table', 'Sliding Window', 'Counting', 'Python', 'Python3']