LeetCode 851 - Loud and Rich

This problem describes a group of people where some people are known to be richer than others. The richer array represents directed relationships between people. If richer[i] = [a, b], it means person a definitely has more money than person b.

leetcodemediumarraydepth-first-searchgraph-theorytopological-sort

LeetCode Problem 851

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Graph Theory, Topological Sort

Solution

Problem Understanding

This problem describes a group of people where some people are known to be richer than others. The richer array represents directed relationships between people. If richer[i] = [a, b], it means person a definitely has more money than person b.

Each person also has a quietness score stored in the quiet array. A smaller value means the person is quieter. The goal is to determine, for every person x, which person among all people who are at least as rich as x has the minimum quietness value.

The phrase "equal to or more money than" is important. Every person is considered at least as rich as themselves, so each person is always a candidate answer for their own result.

The output array answer should satisfy:

answer[x] = the quietest person among everyone richer than or equal to x

This is fundamentally a graph problem. The richer relationships form a directed graph:

a -> b means a is richer than b

Since the problem guarantees that the data is logically consistent, there are no cycles. That means the graph is a Directed Acyclic Graph, or DAG.

The constraints are relatively small:

  • n <= 500
  • The graph can be dense
  • Quietness values are unique

Even though 500 is not huge, a naive solution that repeatedly explores the entire graph for every node can still become inefficient. The DAG property strongly suggests using memoized DFS or topological graph processing.

Several edge cases are important:

  • A person may have no richer people at all
  • The richer array may be empty
  • The quietest richer person may be multiple levels above in the graph
  • The graph may contain disconnected components
  • Every person has a unique quietness value, so ties never occur

Because the graph is acyclic, recursive DFS with memoization works safely without worrying about infinite recursion.

Approaches

Brute Force Approach

The brute force solution is to independently compute all richer people for every person.

For each person x, we can run a DFS or BFS that traverses upward through all richer relationships. During the traversal, we track the quietest person encountered.

This approach is correct because it explicitly explores every person who is richer than x, so the minimum quietness among those people is guaranteed to be found.

However, this method performs a graph traversal starting from every node independently. Since many traversals repeatedly visit the same subgraphs, there is a large amount of duplicated work.

In the worst case, the graph can contain nearly O(n²) edges. Running a traversal from every node leads to approximately O(n * (n + e)) complexity, which becomes inefficient.

Key Insight for the Optimal Solution

The critical observation is that many people share overlapping richer subgraphs.

Suppose we already know the quietest richer person for node 3. If another node points to 3, we should reuse that result instead of recomputing it.

Because the graph is a DAG, we can use DFS with memoization:

  • For each person x, compute the quietest richer person once
  • Store the result
  • Reuse the stored answer whenever needed again

This transforms repeated graph traversals into a dynamic programming problem on a DAG.

The recursive relation is:

answer[x] = quietest among:
- x itself
- all answers of richer neighbors

This avoids recomputation and processes each node and edge only once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × (n + e)) O(n + e) Runs a fresh traversal for every node
Optimal O(n + e) O(n + e) DFS with memoization on a DAG

Here, e represents the number of richer relationships.

Algorithm Walkthrough

  1. Build a directed graph where edges point from poorer people to richer people.

If a is richer than b, then for person b we want access to a. So we store:

b -> a

This direction makes DFS naturally move toward richer people. 2. Create an answer array initialized with -1.

This array serves two purposes:

  • Stores the final answer for each person
  • Acts as a memoization cache

If answer[x] != -1, we already computed the result for x. 3. Define a DFS function for person x.

The DFS returns the index of the quietest person among everyone richer than or equal to x. 4. Initialize the answer for x as x itself.

Every person is at least as rich as themselves, so they are always a candidate. 5. Visit all richer neighbors of x.

For each richer person r:

  • Recursively compute dfs(r)
  • Compare the quietness of the returned candidate against the current best answer
  • Update the answer if a quieter person is found
  1. Store the computed result in the memoization array.

Once computed, future DFS calls can immediately return the cached result. 7. Run DFS for every person from 0 to n - 1.

Some nodes may already be cached from earlier traversals, so they return instantly. 8. Return the completed answer array.

Why it works

The graph is acyclic, so recursive DFS always terminates. For every person x, the DFS explores exactly all people who are richer than or equal to x. The recursion combines the best answers from all richer neighbors, ensuring that the minimum quietness value propagates downward through the graph.

Memoization guarantees that each node's answer is computed exactly once, which eliminates redundant work while preserving correctness.

Python Solution

from typing import List

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

        graph = [[] for _ in range(n)]

        for richer_person, poorer_person in richer:
            graph[poorer_person].append(richer_person)

        answer = [-1] * n

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

            quietest_person = person

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

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

            answer[person] = quietest_person
            return quietest_person

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

        return answer

The implementation begins by constructing an adjacency list. The graph is reversed compared to the input relation because we want to efficiently move from a person toward richer people during DFS.

The answer array is initialized with -1 values. This acts as the memoization cache. Once a person's quietest richer candidate is computed, it is stored permanently.

The dfs function performs the core logic. If the answer already exists, it immediately returns the cached value. Otherwise, the current person is treated as the initial best candidate.

The function then explores all richer neighbors recursively. Each recursive call returns the quietest person reachable from that richer node. By comparing quietness values, the algorithm keeps track of the globally quietest reachable person.

Finally, the computed result is stored in the cache and returned.

The outer loop ensures every person gets processed, including disconnected graph components.

Go Solution

func loudAndRich(richer [][]int, quiet []int) []int {
	n := len(quiet)

	graph := make([][]int, n)

	for _, edge := range richer {
		richerPerson := edge[0]
		poorerPerson := edge[1]

		graph[poorerPerson] = append(graph[poorerPerson], richerPerson)
	}

	answer := make([]int, n)

	for i := 0; i < n; i++ {
		answer[i] = -1
	}

	var dfs func(int) int

	dfs = func(person int) int {
		if answer[person] != -1 {
			return answer[person]
		}

		quietestPerson := person

		for _, richerPerson := range graph[person] {
			candidate := dfs(richerPerson)

			if quiet[candidate] < quiet[quietestPerson] {
				quietestPerson = candidate
			}
		}

		answer[person] = quietestPerson
		return quietestPerson
	}

	for person := 0; person < n; person++ {
		dfs(person)
	}

	return answer
}

The Go implementation closely mirrors the Python solution. Slices are used for the adjacency list and answer array.

Unlike Python, Go does not provide automatic initialization to -1, so the answer array must be explicitly filled with -1.

The recursive DFS is implemented using a function variable declaration because Go requires recursive anonymous functions to be declared before assignment.

Integer overflow is not a concern because all values are bounded by 500.

Worked Examples

Example 1

Input:

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

Step 1: Build the Graph

We reverse edges so poorer people point to richer people.

Person Richer Neighbors
0 [1]
1 [2, 3]
2 []
3 [4, 5, 6]
4 []
5 []
6 []
7 [3]

Step 2: DFS Computation

Start with person 0.

dfs(0)

Explore richer person 1.

dfs(1)

Explore richer person 2.

dfs(2)

Person 2 has no richer neighbors.

answer[2] = 2

Back to person 1.

Current best:

quiet[1] = 2
quiet[2] = 5

Person 1 remains quieter.

Now explore richer person 3.

dfs(3)

Explore neighbors 4, 5, 6.

Results:

Person Quiet
3 4
4 6
5 1
6 7

The quietest is person 5.

answer[3] = 5

Back to person 1.

Compare:

Candidate Quiet
1 2
5 1

Update:

answer[1] = 5

Back to person 0.

Compare:

Candidate Quiet
0 3
5 1

Update:

answer[0] = 5

Final answers:

Person Answer
0 5
1 5
2 2
3 5
4 4
5 5
6 6
7 7

Output:

[5,5,2,5,4,5,6,7]

Example 2

Input:

richer = []
quiet = [0]

Graph:

Person Richer Neighbors
0 []

DFS:

dfs(0)

No richer neighbors exist, so:

answer[0] = 0

Output:

[0]

Complexity Analysis

Measure Complexity Explanation
Time O(n + e) Each node and edge is processed once
Space O(n + e) Adjacency list, recursion stack, and memoization array

The adjacency list stores all edges exactly once, requiring O(e) space. The memoization array requires O(n) space.

Because memoization ensures every node is computed only once, the DFS traverses each edge only a single time across the entire execution. This gives linear complexity relative to the graph size.

Test Cases

from typing import List

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

        graph = [[] for _ in range(n)]

        for richer_person, poorer_person in richer:
            graph[poorer_person].append(richer_person)

        answer = [-1] * n

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

            quietest_person = person

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

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

            answer[person] = quietest_person
            return quietest_person

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

        return answer

solution = Solution()

# Example 1 from the problem statement
assert solution.loudAndRich(
    [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]],
    [3,2,5,4,6,1,7,0]
) == [5,5,2,5,4,5,6,7]

# Example 2, single person
assert solution.loudAndRich([], [0]) == [0]

# Linear richer chain
assert solution.loudAndRich(
    [[1,0],[2,1],[3,2]],
    [4,3,2,1]
) == [3,3,3,3]

# Everyone already quietest themselves
assert solution.loudAndRich(
    [[1,0],[2,0],[3,0]],
    [0,1,2,3]
) == [0,1,2,3]

# Disconnected graph components
assert solution.loudAndRich(
    [[1,0],[3,2]],
    [5,1,4,0]
) == [1,1,3,3]

# Dense graph
assert solution.loudAndRich(
    [[1,0],[2,0],[3,0],[2,1],[3,1],[3,2]],
    [6,5,4,1]
) == [3,3,3,3]

# No richer relationships
assert solution.loudAndRich(
    [],
    [2,0,1]
) == [0,1,2]

# Quietest person several levels above
assert solution.loudAndRich(
    [[1,0],[2,1],[3,2],[4,3]],
    [5,4,3,2,0]
) == [4,4,4,4,4]
Test Why
Problem example 1 Validates full DAG traversal
Problem example 2 Validates smallest input
Linear richer chain Tests deep recursion
Everyone quietest themselves Ensures self-selection works
Disconnected graph Verifies separate components
Dense graph Tests many overlapping paths
No richer relationships Ensures isolated nodes handled correctly
Quietest person several levels above Verifies transitive propagation

Edge Cases

One important edge case occurs when the richer array is empty. In this situation, nobody is known to be richer than anyone else. Every person is therefore only comparable to themselves. A buggy implementation might incorrectly assume every node has neighbors or fail to initialize answers properly. This implementation handles the case naturally because each DFS starts with the person themselves as the initial best candidate.

Another important case is a long transitive chain of richer relationships. For example:

4 > 3 > 2 > 1 > 0

The quietest richer person for 0 may be many levels above. A naive solution that only checks direct neighbors would fail here. The recursive DFS correctly explores all reachable richer people, ensuring transitive relationships are included.

Disconnected graph components are another common source of mistakes. Some people may belong to completely separate richer hierarchies. An implementation that only starts DFS from a single node could miss entire components. This solution explicitly runs DFS for every person, guaranteeing complete coverage of the graph.

A final subtle case is overlapping subgraphs. Multiple people may depend on the same richer subtree. Without memoization, the algorithm would repeatedly recompute the same answers, causing major inefficiency. The cached answer array ensures every person's result is computed exactly once.