Loud and Rich: DFS on a Wealth Graph
You are given n people labeled 0 to n - 1, a list of richer pairs where richer[i] = [a, b] means person a is strictly richer than person b, and a quiet array where quiet[i] is the quietness value of person i. For each person, find the person with the minimum quietness among everyone who is richer than or equal to them (including themselves). Return the answer as an array.
This is LeetCode 851: Loud and Rich, and it comes down to propagating information through a directed graph using DFS with memoization.
Wealth graph: edges point from richer to poorer
Person 0 (q=3) is richest. Person 3 (q=4) is poorest. For person 3, all four people are richer-or-equal, and person 1 (q=2) is the quietest.
Why this problem matters
Loud and Rich is a clean example of "query every node in a DAG about its ancestors." The wealth relationships form a directed acyclic graph (there are no circular wealth chains), and each node needs to know something about all nodes reachable above it. That pattern shows up any time you need to propagate information through a dependency hierarchy.
What makes this problem tricky is the "all richer-or-equal" part. For a given person, you do not just look at direct connections. You need to consider everyone transitively richer. A brute-force BFS from every node works, but it is wasteful because many nodes share the same richer ancestors. DFS with memoization solves this efficiently by caching results and reusing them across overlapping subproblems.
The brute force approach
For each person, you could run a BFS or DFS to find all richer-or-equal people, then pick the quietest one. This works, but it is O(n * (n + e)) in the worst case because you might traverse the entire graph for each person.
def loud_and_rich(richer, quiet):
n = len(quiet)
graph = [[] for _ in range(n)]
for a, b in richer:
graph[b].append(a)
answer = list(range(n))
for person in range(n):
stack = [person]
visited = set()
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
if quiet[node] < quiet[answer[person]]:
answer[person] = node
stack.extend(graph[node])
return answer
This is correct but slow. If the graph has many shared ancestors, you end up recomputing the same reachability information over and over.
The key insight: DFS with memoization on the wealth graph
Build a directed graph where edges point from poorer to richer people. Then for each person, DFS upward through all richer people, caching the "quietest richer-or-equal person" at each node. When you revisit a node that already has a cached answer, return it immediately instead of re-exploring.
The key observation is that answer[person] depends only on answer[richer_neighbor] for each direct richer neighbor. If you have already computed the answer for a richer neighbor, you can reuse it. This turns the problem into a standard DFS with memoization on a DAG.
For each person, the quietest richer-or-equal person is either themselves or the quietest richer-or-equal person of one of their directly richer neighbors. You just take the minimum across all options.
Walking through it step by step
Step 1: Build the graph and initialize answer. Each person starts as their own answer.
answer[i] = i initially. Each person is richer-or-equal to themselves.
Step 2: DFS from person 3. Person 3 has no outgoing edges. Check richer neighbors: 1 and 2.
We need to DFS into persons 1 and 2 first to find who is quietest among their richer-or-equal sets.
Step 3: DFS into person 1, then into person 0. Person 0 has no richer neighbors, so answer[0] = 0.
Person 0 (q=3) is quieter than person 1 (q=2)? No, 2 < 3. But person 0 is richer, so we compare: min quietness among {0,1} is person 1 (q=2). answer[1] = 1.
Step 4: DFS into person 2, reuse cached answer for person 0. Compare quietness values.
Person 0 (q=3) is richer than person 2 (q=5). Since 3 < 5, answer[2] = 0. Person 0 is the quietest richer-or-equal person for person 2.
Step 5: Back to person 3. Combine results from persons 1 and 2. The quietest richer-or-equal person wins.
Candidates for person 3: self (q=4), answer[1] gives person 1 (q=2), answer[2] gives person 0 (q=3). Quietest is person 1 (q=2). answer[3] = 1.
The DFS solution
def loud_and_rich(richer, quiet):
n = len(quiet)
graph = [[] for _ in range(n)]
for a, b in richer:
graph[b].append(a)
answer = [-1] * n
def dfs(person):
if answer[person] != -1:
return answer[person]
answer[person] = person
for richer_person in graph[person]:
candidate = dfs(richer_person)
if quiet[candidate] < quiet[answer[person]]:
answer[person] = candidate
return answer[person]
for i in range(n):
dfs(i)
return answer
Let's break this down.
First, we build an adjacency list where graph[b] contains all people directly richer than person b. For each pair [a, b] in richer, person a is richer than person b, so we add a to graph[b]. This means "from person b, I can look up toward person a."
The answer array starts filled with -1, which acts as our "not yet computed" marker. When dfs(person) is called, it first checks if the answer is already cached. If so, it returns immediately. This is the memoization that prevents redundant work.
If the answer is not cached, we start by assuming the person themselves is the quietest richer-or-equal person (answer[person] = person). Then we DFS into each directly richer neighbor. Each recursive call returns the quietest person in that neighbor's richer-or-equal set. We compare quietness values and keep the minimum.
The outer loop calls dfs(i) for every person. Some of these calls will return instantly because the answer was already filled in by a previous DFS path.
The -1 sentinel works here because valid person IDs are 0 to n - 1. Using -1 as "unvisited" avoids needing a separate visited array. You could also use None, but an integer sentinel keeps the array homogeneous and avoids type-checking overhead.
Complexity analysis
| Metric | Value |
|---|---|
| Time | O(n + e) where e is the number of richer relationships |
| Space | O(n + e) |
Time: Each person is visited at most once by DFS (subsequent visits hit the cache and return immediately). Building the adjacency list takes O(e). The total DFS work across all calls is O(n + e) because every node and edge is processed exactly once.
Space: The adjacency list uses O(n + e). The answer array and the recursion stack each use O(n). Total: O(n + e).
Building blocks
1. Directed graph DFS with memoization
The pattern of caching results at each node during DFS to avoid redundant computation:
def dfs(node):
if memo[node] is not None:
return memo[node]
memo[node] = base_value(node)
for neighbor in graph[node]:
memo[node] = combine(memo[node], dfs(neighbor))
return memo[node]
This is the same structure you see in Course Schedule (where the "memo" is the three-color state) and in Clone Graph (where the memo maps original nodes to clones). The key discipline is always setting the cache entry before recursing into neighbors, so that cycles (if they existed) would not cause infinite recursion. In this problem the graph is a DAG, so cycles are not possible, but the pattern still applies.
2. Graph construction from edge list
Converting a list of directed pairs into an adjacency list:
graph = [[] for _ in range(n)]
for a, b in edges:
graph[b].append(a)
The direction matters. In this problem, [a, b] means "a is richer than b," and we want to traverse from a person toward their richer connections. So the edge goes from b to a in our adjacency list. Getting this direction wrong is one of the most common mistakes in graph problems. Always think about which direction you need to traverse.
Edge cases
- No richer relationships:
richer = []. Every person is only richer-or-equal to themselves.answer[i] = ifor alli. - Linear chain: person 0 is richer than 1, who is richer than 2, and so on. DFS from the poorest person traverses the entire chain once, and all subsequent calls hit the cache.
- Single person:
n = 1, richer = []. The answer is[0]. - All same quietness: when multiple people have the same quietness value, the one encountered first by DFS wins. The problem guarantees all quietness values are distinct, so this does not actually happen.
- Star graph: one person is richer than everyone else. DFS from any person goes to the rich person, caches the result, and all other DFS calls reuse it.
From understanding to recall
You have seen how DFS with memoization propagates the "quietest richer-or-equal person" through the wealth graph. The adjacency list points from poorer to richer, the DFS walks upward, and the cache prevents redundant traversal. The logic is clean once you see it.
But reproducing it under pressure is a different skill. You need to remember the edge direction (poorer to richer), the sentinel value for unvisited nodes, and the comparison logic that picks the minimum quietness. These details are small, but any one of them can trip you up in an interview.
Spaced repetition closes the gap between understanding and fluency. You practice writing the graph construction and the memoized DFS from scratch at increasing intervals. After a few rounds, the pattern flows automatically. You do not re-derive it. You just write it.
Related posts
- Course Schedule - Another directed graph traversal with topological ordering
- Number of Provinces - DFS on an implicit graph structure
- Clone Graph - Graph traversal with node-level memoization
CodeBricks breaks Loud and Rich into its graph-construction and DFS-memoization building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a graph propagation problem shows up in your interview, you do not hesitate. You just write it.