LeetCode 851: Loud and Rich

Problem Restatement

We are given n people labeled from 0 to n - 1.

Each person has:

For every person x, we need to find the quietest person among all people who are at least as rich as x.

This includes:

1. Person x
2. Everyone directly richer than x
3. Everyone indirectly richer than x

Return an array answer, where:

answer[x]

is the index of the quietest person among all people who have at least as much money as person x.

The richer information is logically valid, so it does not contain contradictions or cycles. The richer relations form a directed acyclic graph.

Input and Output

Function shape:

class Solution:
    def loudAndRich(self, richer: list[list[int]], quiet: list[int]) -> list[int]:
        ...

Examples

Consider:

richer = [[1, 0], [2, 1], [3, 1]]
quiet = [3, 2, 5, 4]

The relationships mean:

For person 0, the people who are at least as rich are:

0, 1, 2, 3

Their quiet values are:

The quietest person is person 1, so:

answer[0] = 1

For person 2, nobody in the given information is richer than person 2.

So the only candidate is person 2, and:

answer[2] = 2

First Thought: Brute Force

A direct approach is:

For each person x:

1. Search for every person who is richer than x
2. Also search for people richer than those people
3. Compare quiet values
4. Return the quietest person found

This is graph reachability.

If we perform a fresh DFS or BFS for every person, the same richer chains may be visited many times.

For example, if many people are poorer than person 5, then the richer chain above person 5 may be recomputed repeatedly.

Problem With Brute Force

Let:

n = len(quiet)
m = len(richer)

A fresh graph traversal for every person can cost up to:

O(n * (n + m))

That is too much when the graph has many relationships.

We need to reuse answers.

Key Insight

The answer for a person depends on the answers of people richer than them.

If person a is richer than person b, then when computing the answer for b, we should consider:

1. Person b
2. Person a
3. Everyone at least as rich as person a

So if we already know the answer for a, we can use it directly.

That suggests DFS with memoization.

Build a graph where each edge points from a poorer person to a richer person.

For a relationship:

[a, b]

person a is richer than person b.

So we add:

graph[b].append(a)

Now, starting from any person, DFS follows edges toward richer people.

Algorithm

Create an adjacency list graph.

For each pair [rich, poor] in richer:

graph[poor].append(rich)

Create an answer array:

answer = [-1] * n

Here, answer[x] == -1 means the answer for person x has not been computed yet.

Define dfs(x):

1. If answer[x] is already known, return it.
2. Start with x as the best candidate.
3. For every richer person y in graph[x]:
   1. Compute dfs(y)
   2. Compare the quietness of the returned candidate with the current best candidate
   3. Keep the quieter one
4. Store the result in answer[x].
5. Return answer[x].

Finally, call dfs(i) for every person i.

Correctness

For each person x, dfs(x) considers person x first.

Then it visits every directly richer person y.

For each such y, dfs(y) returns the quietest person among all people who are at least as rich as y.

Since y is richer than x, everyone at least as rich as y is also at least as rich as x.

Therefore, comparing x with every dfs(y) covers all valid candidates for person x.

The graph has no cycles, so the recursive search eventually stops.

Memoization does not change the result. It only reuses a value after it has already been fully computed.

Thus, for every person x, answer[x] is the quietest person among all people with at least as much money as x.

Complexity

The recursion stack can also take up to O(n) space in the longest richer chain.

Implementation

from collections import defaultdict

class Solution:
    def loudAndRich(self, richer: list[list[int]], quiet: list[int]) -> list[int]:
        n = len(quiet)
        graph = defaultdict(list)

        for rich, poor in richer:
            graph[poor].append(rich)

        answer = [-1] * n

        def dfs(person: int) -> int:
            if answer[person] != -1:
                return answer[person]

            best = person

            for richer_person in graph[person]:
                candidate = dfs(richer_person)

                if quiet[candidate] < quiet[best]:
                    best = candidate

            answer[person] = best
            return best

        for person in range(n):
            dfs(person)

        return answer

Code Explanation

We first build the graph:

graph = defaultdict(list)

for rich, poor in richer:
    graph[poor].append(rich)

This means each person points to people known to be richer.

For example:

richer = [[1, 0]]

creates:

graph[0] = [1]

So from person 0, we can move to person 1.

The answer array is also our memo table:

answer = [-1] * n

When answer[person] == -1, that person’s result has not been computed.

Inside DFS:

best = person

A person is always a valid candidate for themselves because the problem asks for people with equal or more money.

Then we inspect every richer person:

for richer_person in graph[person]:
    candidate = dfs(richer_person)

The call dfs(richer_person) gives us the quietest person among all people at least as rich as richer_person.

If that candidate is quieter than the current best, we update:

if quiet[candidate] < quiet[best]:
    best = candidate

At the end, we cache the result:

answer[person] = best

This prevents repeated work when multiple poorer people share the same richer chain.

Testing

def test_loud_and_rich():
    s = Solution()

    richer = [
        [1, 0],
        [2, 1],
        [3, 1],
    ]
    quiet = [3, 2, 5, 4]
    assert s.loudAndRich(richer, quiet) == [1, 1, 2, 3]

    richer = []
    quiet = [0]
    assert s.loudAndRich(richer, quiet) == [0]

    richer = []
    quiet = [2, 0, 1]
    assert s.loudAndRich(richer, quiet) == [0, 1, 2]

    richer = [[0, 1], [1, 2], [2, 3]]
    quiet = [3, 2, 1, 0]
    assert s.loudAndRich(richer, quiet) == [0, 1, 2, 3]

    richer = [[0, 1], [0, 2], [1, 3], [2, 3]]
    quiet = [1, 3, 2, 4]
    assert s.loudAndRich(richer, quiet) == [0, 0, 0, 0]

    print("all tests passed")

test_loud_and_rich()

Test meaning: