Single pass, two pointer, 4ms Java solution beats 100%, O(N) space
Background\nMy first serious attempt was basically this one, but at each loop iteration where I had K unique integers captured, I would manually count the subar
# Background\nMy first serious attempt was basically this one, but at each loop iteration where I had K unique integers captured, I would manually count the subarrays possible within that range. I would do this by counting how many indices on the left pointed to duplicate values. Looking at other solutions I realized that I don\'t need to count every time as I can remember how many "extra" copies of the unique integers I had at the left of the range and that count was the number of subarrays represented (count+1 actually). It tended towards O(N) in practice, but the extra counting at each step could drive it to a higher complexity if the entire array ended up being one big long valid subarray.\n\nMany of the variations of this counting method use a Map for storing the counts, and that is a similar O(N) time complexity to this solution, but slows down the operation of each step compared to using a bucket sort and may use more storage depending on how much you thrash the storage of the Map.  The definition of the problem carefully limits the range of integers you can find in the array to 1..N where N is the size of the data array.  So, accepting O(N) space usage, we can use bucket sorting which is much faster.\n\nI\'ll note that I also used a loop at one point for the "if (K < 0)" case thinking that I had to pass up all values until I found one whose count went to 0.  I noticed a solution that didn\'t use a loop there and realized that if you\'ve already skipped the left pointer past all of the "extra" values (counting them so you know how many subarrays are represented), then the value at the left pointer should be unique, and its count should be 1 exactly.  Thus, you always have at most one value to advance the left pointer past before you are down to the intended number of unique integers in the range.\n\nI am not sure why this runs more than 2ms faster than any other Java solution as there is nothing unique here that isn\'t already used in any number of the other discussion examples, but its run time is consistently shown 2 stops faster than any other recorded solution.\n\nHere is a more formal description of the way it works.\n\n# Observations\n- First note that a given range of unique integers can exist within the array with duplicates, such as in **[1,2,1,2]**. For **K=2** that is an example of one of the valid subarrays to be counted, but it also contains further subarrays that should also be counted.\n- We can exhaustively count all possible subarrays of that range of 4 values, but things get complicated depending on the pattern of the repeated integers.\n- To break it down, we can find the first unique subarray that starts at the first value and contains all of the integers - [**1,2**,1,2].  It has no further subarrays that also count, so we only get 1 subarray at that position.\n- Moving to the right by one, we can count all unique subarrays that end at the next index - [1,**2,1**,2] and [**1,2,1**,2]\n- Finally we move again to the right and count all unique subarrays that end at the last index - [1,2,**1,2**], [1,**2,1,2**], and [**1,2,1,2**]\n- At each of those stages we are simply counting 1 for the minimal valid subarray that ends at the specified index plus 1 more for each of the duplicate values to the left of that minimal subarray.\n- We don\'t recount former subarrays in the latter stages because each stage only counts subarrays that end at the new position and all of the previously counted subarrays ended at an earlier position.\n\n# Overview of algorithm\n- For each index **r** in the array of input values starting with the smallest **r** that encompasses **K** unique integers:\n  - find the smallest subarray of **K** unique integers that ends at **r**\n  - count the number of contiguous values (**ndup**) to the left of that subarray that are duplicates of the same **K** unique integers\n  - new subarrays discovered that end at **r** will be **(ndup + 1)**, add that number to the total\n\n# Loop invariants\n\n- At the start of each loop iteration we have two pointers framing a section of the input array that contains no more than K unique integers.\n- **l** and **r** represents the section of unique integers such that any index **i** of the data array where **(l <= i < r)** is in the range, aka the half-open interval **[l -> r)**.\n- No smaller subarray that also ends at **r** contains the same unique integers so this is the minimal subarray that ends at **r** which has at most K unique integers.\n- Similarly **l** is a pointer to the first number in the input that is not duplicated in the range **[l -> r)**.\n- **nsub** represents the number of unique subarrays that also contain the same unique integers that are in the range and is basically a count of the number of duplicates of these integers that lie to the left of **l**, plus one for the minimal subarray from **[l -> r)**.\n- **nvals[]** array keeps a count of each integer within the range **[l -> r)**.  If the count is 0, that particular integer does not appear in the range.  If the count is 1, then that particular integer appears only once in the range. If the count is greater than 1, then that integer appears multiple times within the range.\n- Since **[l -> r)** is the smallest subarray with **K** unique integers, then the value at index **l** should  have no other duplicates in the range.\n- As we grow the range to include more indices (by convention, always at the right end of the range by moving **r** forward), we increment the location in the **nvals** array associated with the new value at **A[r]**.  If that count goes from 0 to 1, then we have added a new unique integer to the range.\n- As we shrink the range to include fewer indices (by convention, always at the left end of the range by moving **l** forward), we decrement the associated location in the **nvals** array.  If that count goes from 1 to 0, then we have removed all instances of that integer from the range.\n- Due to the above properties, at the start of a loop iteration we can thus prove that **nvals[l]** is 1 because it is the first integer that is not duplicated in the range.\n- Rather than keep a separate count of the number of unique integers in the range, we simply use the **K** value to represent how many more unique values we need to add to the range. If it is positive then we need more unique integers, if it is negative we have too many, and if it is 0, then we have a valid range.\n- Summary:\n  - **[l->r)** is the minimal subarray ending at **r** with at most **K** unique integers\n  - value at **l** is unique within the range **[l -> r)** and so **(nvals[A[l]] == 1)**\n  - **K** reaches 0 as soon as we have a valid subarray with **K** unique integers\n  - **K** never varies from **[0,-1]** from that point on\n\n# Operation of the loop\n- The first thing that each loop iteration does is to add a new value to the range at **r**.  We adjust the count for that value and if the count used to be 0 then we decrement **K** to represent the inclusion of one more unique integer in the range.\n- If **K** becomes negative (it will be -1 exactly), then we have too many unique integers in the range and so we need to remove one.  Due to the properties above, we know that simply getting rid of the element at **l** will reduce the unique integers back to the appropriate number since we left it pointing to the first unique integer in the former valid range. In doing so, we no longer have any additional valid subranges to the left of **l** (since we know that the value at **l** itself is no longer in the valid range) so we reset the number of valid subarrays **nsub** to 1 (it may grow again in a later stage of the loop that counts duplicates).\n- In early passes of the loop before we\'ve passed **K** unique integers, the value of **K** may be positive at this point in which case we loop around, but once we get going it will tend to be **(K == 0)** at this point.\n- If **(K == 0)** then **[l -> r)** is a valid range with exactly **K** integers, but it may not be the smallest such range that ends at **r**.\n  - First we loop and bump **l** as long as it points to numbers that appear more than once in the range (**while (nvals[A[l]] > 1)**)\n  - (Note that it is impossible for **(nvals[A[l]] == 0)** in this loop because all numbers between **l** and **r** are in the list of unique integers at least once.)\n  - (Also note that it is impossible for **l** to advance off the end of the **A[]** array because it will always find a unique value before then.)\n  - For each bump of **l** we adjust the counts in the **nvals[]** array and we increment **nsub** as we have identified one more duplicate integer to the left of **l**\n  - When that loop terminates by finding a value such that **(nvals[A[l]] == 1)** then we have again found the smallest valid subarray ending at **r**.\n  - Finally, we can add the number of represented subarrays - **nsub** - to the total\n\n# Java implementation\n```\n    public int subarraysWithKDistinct(int[] A, int K) {\n        int nvals[] = new int[A.length + 1];\n        int nsub = 1;\n        int l = 0;\n        int r = 0;\n        int totalsub = 0;\n        while (r < A.length) {\n            if (nvals[A[r++]]++ == 0) {\n                K--;\n            }\n            if (K < 0) {\n                --nvals[A[l++]];\n                K++;\n                nsub = 1;\n            }\n            if (K == 0) {\n                while (nvals[A[l]] > 1) {\n                    --nvals[A[l++]];\n                    nsub++;\n                }\n                totalsub += nsub;\n            }\n        }\n        return totalsub;\n    }\n```
[]