Abstract / Summary

Find the kth unique string in an array when strings are considered in their first appearance order.

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 82% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Counting
• Hash Table
• String

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 provided implementation defines a method that returns the k-th distinct string from an input list while preserving the original order. It first builds a frequency map for all strings, then iterates a second time to locate the k-th element whose count equals one. If fewer than k distinct strings exist, an empty string is returned.

Frequency Counting

The algorithm begins by constructing a dictionary that records how many times each string appears.

freq = defaultdict(int)
for a in arr:
    freq[a] += 1

Using defaultdict(int) eliminates the need for explicit existence checks, allowing the count to be incremented directly. This step aggregates the occurrence information in a single pass over the input list.

Identifying the k-th Distinct Element

After the frequency map is ready, a second traversal scans the original list in order.

seen = 0
for a in arr:
    if freq[a] == 1:
        seen += 1
        if seen == k:
            return a

The variable seen tracks how many distinct strings have been encountered so far. When the count matches the requested position k, the corresponding string is returned immediately, ensuring the earliest qualifying element is selected.

Edge Cases Handled

When the input list contains no distinct strings, the frequency map will have counts greater than one for every entry, causing the inner condition freq[a] == 1 never to be satisfied. Consequently, the loop completes without a return, and the method falls through to the final statement, yielding an empty string.

If k exceeds the total number of distinct strings, the same fallback occurs, returning an empty string as a sentinel value.

An empty input list also follows this path: the frequency map remains empty, the second loop does not execute, and the method returns the empty string, gracefully handling the degenerate case without error.

Performance Optimizations

The code leverages two linear passes over the data, each performing constant-time dictionary operations. By using defaultdict, it avoids conditional branches that would otherwise be required to initialize dictionary entries, reducing overhead.

Early termination is another implicit optimization: as soon as the k-th distinct string is found, the method returns immediately, preventing unnecessary processing of the remaining elements. This is particularly beneficial when k is small relative to the list size.

The choice of a hash-based dictionary for frequency tracking ensures that lookups and updates execute in amortized constant time, contributing to overall efficiency.

Overall, the implementation balances clarity with effective use of Python’s built-in data structures to achieve a concise solution that scales well with input size.

Imagine a long train filled with colorful toy blocks. Some blocks are exactly the same, like two red squares, while other blocks are one of a kind. This code helps pick out a special block from the train.

First, the computer looks at every single block in the train and keeps a tiny notebook. Whenever it sees a block, it writes down how many times that specific color appears in the notebook. By the time it finishes looking at every block, it knows exactly which ones are unique because they appear only one time in the notebook.

Next, the computer walks along the train again from the beginning to the end. Every time it finds a block that is one of a kind, it counts it. It keeps counting these special blocks until the count reaches the lucky number that was asked for. As soon as the count matches that number, the computer points to that specific block. It is just like playing a game of hide and seek to find the one that stays hidden the right amount of times.

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	C++	Python		Java					TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python	JS	Java		Go		Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	chandansgowda		Python
	charles-wangkai				Java
	everthis			JS
	fartem					Ruby
	fsq	C++
	JoshCrozier			JS
	lkwq007		Python
	muhammadfarhankt						Go
	suxrobGM							C#
	varunu28				Java
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
muhammadfarhankt	Go
suxrobGM	C#
varunu28	Java
withaarzoo	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