Abstract / Summary

Count the number of continuous parts in a list of numbers that contain exactly k different values.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 68% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Counting
• Hash Table
• Sliding Window

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation solves the problem of counting subarrays that contain exactly k distinct integers. It follows a sliding-window strategy that first builds the left-most window that satisfies the distinct-count requirement and then iterates through the array, adjusting the window while accumulating the result. The code relies on a frequency dictionary to track the number of occurrences of each integer inside the current window.

Initialization

The algorithm starts by positioning two pointers, left and right, at the beginning of the input list. A defaultdict(int) named freq is created to store the frequency of each element inside the window.

left = right = 0
freq = defaultdict(int)

Expanding to First Valid Window

A while loop advances the right pointer and updates freq until either the window contains k distinct values or the end of the list is reached. This loop guarantees that the first window examined is the left-most one that could be valid.

while len(freq) < k and right < len(nums):
    freq[nums[right]] += 1
    right += 1

If the loop finishes with fewer than k distinct numbers, the function returns zero because no subarray can satisfy the condition.

if len(freq) < k:
    return 0

Main Loop

The core of the solution is an infinite while True loop that repeatedly counts subarrays starting at the current left position, then moves the window one step to the right, and finally readjusts the left side to maintain exactly k distinct elements.

result = 0
while True:
    ...

Counting Subarrays

Inside the main loop a copy of the current frequency map, current, is made. A for loop iterates from left up to right, representing the possible end positions of subarrays that start at left. For each iteration the result counter is incremented, then the element at the scanning position is virtually removed from current. When the removal would eliminate a distinct integer (its count drops to zero), the inner loop breaks, because any longer subarray would contain fewer than k distinct numbers.

current = freq.copy()
for scan in range(left, right):
    result += 1
    slideout = nums[scan]
    current[slideout] -= 1
    if current[slideout] == 0:
        break

Extending Right Boundary

After counting subarrays for the current left position, the algorithm checks whether the right pointer has reached the end of the array. If it has, the outer loop terminates.

if right == len(nums):
    break

Otherwise the element at right is added to freq, and right is advanced by one, thereby expanding the window to include a new element.

freq[nums[right]] += 1
right += 1

Shrinking Left Boundary

The window may now contain more than k distinct integers. A while loop removes elements from the left side until the distinct count returns to k or fewer. When the frequency of the element at left is greater than one, only its count is decremented; otherwise the key is deleted from the dictionary, effectively reducing the distinct count. The left pointer is incremented after each adjustment.

while len(freq) > k:
    slideout = nums[left]
    if freq[slideout] > 1:
        freq[slideout] -= 1
    else:
        del freq[slideout]
    left += 1

When the distinct count drops back to exactly k, the outer loop repeats, counting new subarrays that start at the updated left.

Edge Cases Handled

The code explicitly handles the situation where the entire array contains fewer than k distinct values; it returns zero without entering the main counting phase. When the right pointer reaches the end of the list, the algorithm stops after processing the final set of subarrays, ensuring no out-of-range access. During the counting phase, the inner loop stops as soon as a distinct integer would be lost, which correctly prevents counting subarrays that fall below the required distinct count. The removal logic distinguishes between decreasing a count and deleting a key, thereby maintaining an accurate distinct-element count even when an element appears multiple times.

Performance Optimizations

The solution leverages a sliding-window approach that moves each pointer at most once across the array, avoiding repeated scans of the same region. Using defaultdict(int) eliminates the need for explicit existence checks before incrementing frequencies, reducing overhead. Copying the frequency map only when counting subarrays (once per outer iteration) isolates the mutable state needed for the inner scan, preventing side effects on the main freq structure. Early termination when the distinct count is insufficient prevents unnecessary work on inputs that cannot produce any valid subarray. The inner counting loop breaks immediately after the distinct count would drop, limiting the number of iterations to the exact number of subarrays that satisfy the condition for the current left position.

The combination of these techniques yields a solution that processes the input in linear time relative to the length of nums, while using only a modest amount of auxiliary storage for the frequency dictionaries.

Imagine you have a long train made of colorful blocks. Some blocks are red, some are blue, and some are green. This code is a clever helper that looks for small sections of the train that have exactly the right amount of colors inside.

The code starts by grabbing a handful of blocks until it finds just enough different colors. This is like holding a magnifying glass over a piece of the train. It keeps track of how many of each color it sees in a little imaginary notebook.

Once it has the right number of colors, it starts moving down the train. It checks to see how many different ways it can make a group of those blocks while keeping the count of colors perfect. If it finds too many different colors, it slides the front part of its magnifying glass forward to drop a block off. If it finds too few, it pulls more blocks in from the back.

It keeps scooting along the train like a caterpillar, expanding and shrinking its reach to make sure every group it counts follows the rules. It keeps doing this until the whole train has been checked from beginning to end.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python						TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python				Go
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fsq	C++
	gouthampradhan		Java
	halfrost							Go
	JoshCrozier				JS
	martianoff						Scala
	pruthvikp			Python
	shreymehul					C#
	suxrobGM					C#
	trung-hn			Python
	varunu28		Java
	vli02								C
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
martianoff	Scala
pruthvikp	Python
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality