Abstract / Summary

Given an array and a window size, count how many elements in each window are unique.

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 38% (90k+ submissions).

Typical patterns to solve this problem:

• Array
• 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 computes the “beauty” of every contiguous sub-array of length k in nums. For each window the beauty is defined as the x-th smallest negative number, or 0 when the window contains fewer than x negative values. The algorithm walks the array with a sliding window, maintains a frequency table for negative values, and reuses the previously computed beauty whenever possible.

Sliding-window preparation

The code begins by allocating a fixed-size list have of length 51. Because the problem limits negative numbers to the range [-50, -1], each index directly corresponds to a possible negative value, and the list entry stores its current count inside the window.

have = [0] * 51          # index 0 corresponds to -0 (unused), index 1 to -1, …, index 50 to -50
for n in nums[:k - 1]:
    if n < 0:
        have[n] += 1

Only the first k-1 elements are processed at this stage, leaving the rightmost element of the first full window to be added in the main loop. The variable total tracks the total number of negative elements currently present:

total = sum(have)

Main iteration

The core loop iterates over pairs (left, right) where right is the element entering the window and left is the element leaving it. The zip construction aligns the original list with the slice that starts at index k-1, guaranteeing that each iteration corresponds to a single slide of the window.

Adding the new element

When the incoming element right is negative, its count is incremented and total is updated. If right is more negative than the previously reported beauty (previous), the cached answer is invalidated by resetting previous to 0.

if right < 0:
    have[right] += 1
    total += 1
    if right < previous:
        previous = 0

Determining the beauty for the current window

Three mutually exclusive cases are evaluated:

1. Cached answer still valid - when previous is negative, the order of negatives has not changed, so the same beauty can be yielded directly.

    if previous < 0:
        yield previous

2. Insufficient negatives - when total is smaller than x, the window does not contain enough negative numbers, and the beauty is defined as 0.

    elif total < x:
        yield 0

3. Exact computation required - otherwise the algorithm scans the frequency table from the most negative value upward, accumulating counts until reaching the x-th negative. The loop stops as soon as the cumulative count meets or exceeds x, and the current index i (a negative number) is the answer. The result is cached in previous for possible reuse in the next iteration.

    else:
        negative = 0
        for i in range(-50, 0):
            if negative + have[i] >= x:
                break
            negative += have[i]
        yield i
        previous = i

Removing the leftmost element

After the answer for the current window is emitted, the element that exits the window (left) is processed. If it is negative, its count and the total negative counter are decremented. When the departing element is less than or equal to the cached answer, the cache is cleared because the previously reported beauty may no longer be present in the next window.

if left < 0:
    have[left] -= 1
    total -= 1
    if left <= previous:
        previous = 0

Edge-case handling

The algorithm gracefully handles windows that contain no negative numbers: total becomes 0, the elif total < x branch yields 0. When the window has exactly x negatives, the scanning loop stops precisely at the x-th negative, returning the correct value. The reset of previous whenever a more negative element enters or an element equal to the cached answer leaves ensures that the cached result is never stale, even when the multiset of negatives changes without altering the order of the smallest x values.

Performance optimizations

The use of a fixed-size array have eliminates the need for dynamic data structures such as dictionaries or heaps, providing O(1) updates for insertions and deletions. The scanning loop iterates over at most 50 entries, which is a constant bound independent of the input size. By caching the previously computed beauty in previous and reusing it whenever the relative order of negatives does not change, the algorithm avoids repeating the scan for many consecutive windows, reducing the average work per slide. The early break in the scan (if negative + have[i] >= x: break) stops the loop as soon as the required count is reached, preventing unnecessary iteration over the remaining negative values. All these choices keep the per-window work minimal and deterministic.

Imagine a long line of numbered cards lying on a table. This code uses a small window that slides across the line one step at a time, just like a toy car driving along a track. The goal is to peek at all the cards inside the window to see which ones have a special negative number written on them.

Before the car starts moving, it looks at the first few cards to see how many negative numbers are already there. It keeps a secret tally sheet to remember how many times each specific negative number appears.

As the toy car slides forward, it adds a new card that appears at the front and drops the old card that falls off the back. Every time the car stops, it checks its tally sheet. It starts counting from the smallest negative number upwards until it reaches the target amount requested. Once it finds the winning number that equals that target, it writes that number down.

If there are not enough negative numbers hiding in the window, it just writes down zero instead. After it finishes checking the window, it puts the old card away and updates the tally sheet so it is ready for the next stop. This continues until the toy car reaches the very end of the line of cards.

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

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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		Python	Java	C++		TS
	WalkCCC		Python	Java	C++
	leetcode.ca		Python	Java	C++	Go	TS
	Progiez		Python	Java	C++
github	charles-wangkai			Java
	everthis	JS
	fsq	JS
	lkwq007		Python
	wisdompeak				C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	JavaScript
lkwq007	Python
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