Abstract / Summary

Given a list of numbers, quickly pick a random index where the value is a specific target.

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 64% (400k+ submissions).

Typical patterns to solve this problem:

• Hash Table
• Math
• Randomized
• Reservoir Sampling

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 class implements a compact solution for selecting a random index of a given target value from an immutable list of integers. The constructor builds an auxiliary data structure that groups all positions of each distinct number, and the pick method retrieves a random position from the pre-computed group. By separating the preprocessing from the query, the design achieves constant-time random selection after a single linear pass over the input.

Initialization

During object creation the code iterates over the input list once, recording the index of each element in a dictionary whose keys are the element values and whose values are lists of indices. The use of defaultdict(list) eliminates the need for explicit existence checks before appending a new index.

class Solution:
    def __init__(self, nums: List[int]):
        self.pos = defaultdict(list)
        for where, what in enumerate(nums):
            self.pos[what].append(where)

The loop variable where holds the current index, while what holds the element at that index. Each index is appended to the list associated with its element value, producing a mapping such as {5: [0, 3, 7], 2: [1, 4]} for an example input. This preprocessing step runs once per instance and prepares the data for fast queries.

Random Selection

The pick method receives a target integer and returns a randomly chosen index from the list stored for that target. It relies on random.choice, which selects an element uniformly from a non-empty sequence.

    def pick(self, target: int) -> int:
        return choice(self.pos[target])

Because the dictionary entry for target is a list of all its occurrences, the method directly accesses the pre-computed list and delegates the randomness to the standard library. The call is a single dictionary lookup followed by a constant-time random selection.

Edge Cases Handled

When the input list contains multiple occurrences of the same value, the dictionary entry aggregates all corresponding indices, ensuring that pick can return any of them with equal probability. If a value appears only once, the list for that key contains a single element, and choice will always return that index, which is a correct deterministic outcome for the single-occurrence case. The use of defaultdict guarantees that the dictionary always returns a list object, so the code does not need to guard against missing keys during construction.

Performance Optimizations

The primary optimization is the separation of preprocessing from query time. By constructing the pos mapping in a single linear scan, the solution avoids repeated scans of the original list for each pick call. The dictionary provides O(1) average-case access to the list of indices for any target, and random.choice operates in O(1) on a Python list because it selects an element by index. The choice of defaultdict removes conditional logic for key initialization, reducing overhead in the construction loop. Together, these choices yield a highly efficient implementation for scenarios with many pick operations after a one-time setup.

Imagine having a big collection of colorful building blocks in a box. Each block has a special number painted on it. This code starts by looking through the whole box and making a list of where every number is hiding. It keeps track of these spots in a special notebook so it remembers exactly which pile each number belongs to.

When it comes time to pick a specific number, the code opens that notebook to the right page. It sees all the different places where that number is hiding and selects one of those spots at random. It is just like reaching into a box and pulling out one toy when there are many identical ones waiting to be chosen.

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++	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
	fartem						Ruby
	fengvyi	C++
	gouthampradhan		Java
	haoel	C++
	JoshCrozier				JS
	linouk23	C++
	lkwq007			Python
	lzl124631x	C++
	ruoru					Rust
	suxrobGM							C#
	varunu28		Java
	vli02								C
	XiaotaoGuo	C++
	YuriSpiridonov			Python
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
fartem	Ruby
fengvyi	C++
gouthampradhan	Java
haoel	C++
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
vli02	C
XiaotaoGuo	C++
YuriSpiridonov	Python

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