Abstract / Summary

You must assign each person in a group as either loud or rich so that everyone meets the requirements of their assigned type.

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

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 solves the “loud and rich” problem by first building a reverse adjacency structure that maps each person to the set of people who are directly richer than them. It then iteratively expands these sets until every person’s set contains all richer individuals reachable through any number of steps. Finally, it walks through each person’s accumulated richer set to pick the quietest individual, yielding the answer as a generator.

Building the reverse adjacency

snobs = defaultdict(set)
for a, b in richer:
    snobs[b].add(a)

The loop processes each pair [a, b] where a is richer than b. By inserting a into snobs[b], the code creates a mapping from a person to all people who are immediately richer. Using a defaultdict(set) ensures that missing keys are created automatically and that duplicate entries are collapsed, keeping the structure compact.

Detecting persons with no richer ancestors

final = [ len(snobs[i]) == 0 for i in range(size) ]

A boolean list final records whether the richer set for a given index is already complete. If a person has no direct richer entries (len(snobs[i]) == 0), the corresponding flag is set to True. This early identification allows the later propagation loop to skip work for those individuals.

Iterative propagation of richer relationships

again = True
while again:
    again = False
    for i in range(size):
        if not final[i]:
            done = True
            for s in list(snobs[i]):
                if final[s]:
                    snobs[i] |= snobs[s]
                else:
                    done = False
            if done:
                final[i] = True
            else:
                again = True

The outer while loop continues until no further changes occur. Inside, each person whose richer set is not yet finalized is examined. For every richer person s already marked as final, the code merges snobs[s] into snobs[i] using the set union operator |=. This step propagates indirect richer relationships without revisiting already settled nodes. The done flag tracks whether all richer ancestors of i have been resolved; if so, final[i] is set to True. The again flag ensures that the loop repeats only when at least one person still requires processing, preventing unnecessary iterations.

Selecting the quietest person in each richer set

for i in range(size):
    low = i
    for s in snobs[i]:
        if quiet[s] < quiet[low]:
            low = s
    yield low

After the propagation phase, each snobs[i] contains every person richer than i, directly or indirectly. The inner loop scans this set, comparing the quiet values to find the minimum. The variable low is initialized to i so that a person can be selected as their own answer when no quieter richer individual exists. The function yields the index of the quietest reachable person for each i, producing a lazy sequence that can be consumed as a list by the caller.

Edge-case handling

When the richer list is empty, the initial construction of snobs leaves every entry as an empty set. Consequently, final is populated with True for all indices, the propagation loop exits immediately, and the final selection loop simply yields each index itself, correctly reflecting that no richer person exists.

If quiet contains a single element, size becomes 1. The adjacency map contains at most one empty set, final is [True], and the generator yields 0, handling the minimal input size without special casing.

The algorithm also gracefully manages situations where multiple richer relationships converge on the same person. Because snobs stores sets, duplicate richer entries are collapsed, and the union operation merges them without redundancy. The iterative propagation ensures that even long chains of richer relationships are fully resolved before the quietness comparison, covering transitive cases automatically.

Performance considerations

The use of defaultdict(set) provides O(1) average-time insertion for building the adjacency map and eliminates the need for explicit existence checks. Storing richer ancestors as sets enables fast union operations (|=) that combine entire collections in a single step, reducing the number of element-wise insertions.

The final flag array acts as a memoization layer: once a person’s richer set is complete, subsequent iterations skip any further processing for that index. This prevents repeated scanning of already settled nodes and limits the number of passes through the outer while loop.

Converting snobs[i] to a list before iterating (for s in list(snobs[i])) safeguards against modification of the set during iteration, allowing the union operation to safely expand the set in place without raising runtime errors.

By yielding results lazily, the function avoids constructing an intermediate list of answers, which can be advantageous when the caller consumes the generator incrementally. This design choice reduces peak memory usage, especially for large inputs.

Imagine a big group of people who are trying to figure out who is the quietest among everyone who has at least as much money as them.

First, think about money. The code looks at a list of pairs where it says one person is richer than another. It makes a map to keep track of who is richer than whom, sort of like a family tree that shows who has more pennies in their piggy bank.

Next, it needs to find all the people who are richer than each specific person. This is like playing a game of tag where you try to find everyone in a long line. It keeps checking the list over and over again until it knows every person who is richer than everyone else. If one person is richer than another, and that other person is richer than you, then the first person is definitely richer than you, too. The code connects all these dots so it really understands the full picture of who has more money.

Finally, it looks at everyone one last time. For each person, it checks the quietness score of everyone who is richer than them and also the person themselves. It picks the person with the smallest score, which means they are the quietest of that bunch. It remembers this quietest person for each spot in the group.

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

Time: polynomial
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			Java	Go		TS
	LeetcodeHelp	C++	Python			Java
	Progiez	C++	Python			Java
github	black-shadows	C++
	charles-wangkai					Java
	everthis			JS
	fsq	C++
	halfrost						Go
	JoshCrozier			JS
	lkwq007		Python
	ruoru				Rust
	suxrobGM							C#
	trung-hn		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
zfang399	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