851. Loud and Rich - Solution & Explanation

The problem

There is a group of n people labeled from 0 to n - 1 where each person has a different amount of money and a different level of quietness.

You are given an array richer where richer[i] = [a_i, b_i] indicates that a_i has more money than b_i and an integer array quiet where quiet[i] is the quietness of the i^th person. All the given data in richer are logically correct (i.e., the data will not lead you to a situation where x is richer than y and y is richer than x at the same time).

Return an integer array answer where answer[x] = y if y is the least quiet person (that is, the person y with the smallest value of quiet[y]) among all people who definitely have equal to or more money than the person x.

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]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but it is not clear if they have more money than person 0.
answer[7] = 7.
Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7.
The other answers can be filled out with similar reasoning.

Example 2:

Input: richer = [], quiet = [0]
Output: [0]

Constraints:

n == quiet.length
1 <= n <= 500
0 <= quiet[i] < n
All the values of quiet are unique.
0 <= richer.length <= n * (n - 1) / 2
0 <= a_i, b_i < n
a_i!= b_i
All the pairs of richer are unique.
The observations in richer are all logically consistent.

Approach overview

Problem Overview: You are given a list of richer relationships where richer[i] = [a, b] means person a is richer than b. For every person x, return the person who is the quietest among everyone who has at least as much money as x (including themselves).

Approach 1: Graph Representation and DFS with Memoization (Time: O(n + m), Space: O(n + m))

The relationships naturally form a directed graph. If a is richer than b, then b can reach a when searching for richer people. Build an adjacency list where each node points to people who are richer than it. For every person, run a DFS to explore all reachable richer nodes and track the index with the smallest quiet value. Memoization stores the result for each node so the DFS for that person runs only once. This avoids recomputation and keeps the complexity linear in the number of people and edges.

This approach works well because each node's answer depends only on nodes above it in the "richer" hierarchy. DFS combined with caching effectively turns the graph into a dynamic programming problem over a graph. The recursion explores richer neighbors, compares quietness values, and propagates the best candidate back to the caller. Using memoization ensures each node's quietest richer person is computed a single time.

Approach 2: Topological Sort Based Approach (Time: O(n + m), Space: O(n + m))

Another way to view the problem is information propagation along a DAG. If a is richer than b, the quietest candidate for a could influence the answer for b. Build edges from richer to poorer and compute indegrees. Start with nodes that have no richer prerequisites and process them using a topological order.

During traversal, propagate the quietest known person along outgoing edges. If the quietest person reachable from a is quieter than the current candidate for b, update b's answer. This continues until all nodes are processed. Because the graph is processed once in topological order, the total runtime stays linear. This approach highlights the problem as a dependency flow across a topological sort in a directed graph.

Recommended for interviews: The DFS with memoization solution is the most commonly expected approach. It clearly shows understanding of depth-first search, graph traversal, and caching overlapping subproblems. The topological sort solution is equally optimal but slightly less intuitive at first glance. Showing the DFS solution quickly and mentioning the topological alternative demonstrates strong graph problem-solving skills.

Approach 1: Graph Representation and DFS with Memoization

This approach involves representing the problem as a directed graph, where each edge indicates that one person is richer than another. We perform a Depth-First Search (DFS) from each node to find the quietest person that can potentially reach the given node using memoization to optimize the search process.

Python

def loudAndRich(richer, quiet):
    from collections import defaultdict

    graph = defaultdict(list)
    for u, v in richer:
        graph[v].append(u)

    answer = [-1] * len(quiet)

    def dfs(node):
        if answer[node] != -1:
            return answer[node]
        answer[node] = node
        for nei in graph[node]:
            cand = dfs(nei)
            if quiet[cand] < quiet[answer[node]]:
                answer[node] = cand
        return answer[node]

    for i in range(len(quiet)):
        dfs(i)
    return answer

Java

import java.util.*;

public int[] loudAndRich(int[][] richer, int[] quiet) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    for (int i = 0; i < quiet.length; i++) {
        graph.put(i, new ArrayList<>());
    }
    for (int[] pair : richer) {
        graph.get(pair[1]).add(pair[0]);
    }
    int[] answer = new int[quiet.length];
    Arrays.fill(answer, -1);

    for (int i = 0; i < quiet.length; i++) {
        dfs(i, quiet, answer, graph);
    }
    return answer;
}

private int dfs(int node, int[] quiet, int[] answer, Map<Integer, List<Integer>> graph) {
    if (answer[node] != -1) return answer[node];
    answer[node] = node;
    for (int nei : graph.get(node)) {
        int cand = dfs(nei, quiet, answer, graph);
        if (quiet[cand] < quiet[answer[node]]) {
            answer[node] = cand;
        }
    }
    return answer[node];
}

C++

#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
    int n = quiet.size();
    unordered_map<int, vector<int>> graph;
    for (auto& pair : richer) {
        graph[pair[1]].push_back(pair[0]);
    }
    vector<int> answer(n, -1);

    function<int(int)> dfs = [&](int node) {
        if (answer[node] != -1) return answer[node];
        answer[node] = node;
        for (int nei : graph[node]) {
            int cand = dfs(nei);
            if (quiet[cand] < quiet[answer[node]]) {
                answer[node] = cand;
            }
        }
        return answer[node];
    };

    for (int i = 0; i < n; ++i) {
        dfs(i);
    }
    return answer;
}

JavaScript

var loudAndRich = function(richer, quiet) {
    let n = quiet.length;
    let graph = Array.from({length: n}, () => []);
    for (let [u, v] of richer) {
        graph[v].push(u);
    }
    
    let answer = Array(n).fill(-1);

    const dfs = (node) => {
        if (answer[node] !== -1) return answer[node];
        answer[node] = node;
        for (let nei of graph[node]) {
            let cand = dfs(nei);
            if (quiet[cand] < quiet[answer[node]]) {
                answer[node] = cand;
            }
        }
        return answer[node];
    };

    for (let i = 0; i < n; i++) {
        dfs(i);
    }
    return answer;
};

using System;
using System.Collections.Generic;

public class Solution {
    public int[] LoudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.Length;
        var graph = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        foreach (var pair in richer) {
            graph[pair[1]].Add(pair[0]);
        }

        int[] answer = new int[n];
        Array.Fill(answer, -1);

        for (int i = 0; i < n; i++) {
            Dfs(i, quiet, answer, graph);
        }
        return answer;
    }

    private int Dfs(int node, int[] quiet, int[] answer, Dictionary<int, List<int>> graph) {
        if (answer[node] != -1) return answer[node];
        answer[node] = node;
        foreach (var nei in graph[node]) {
            int cand = Dfs(nei, quiet, answer, graph);
            if (quiet[cand] < quiet[answer[node]]) {
                answer[node] = cand;
            }
        }
        return answer[node];
    }
}

We create a directed graph where each node is a person and there is an edge u -> v if u is richer than v. We then perform a DFS from each node to determine the quietest person reachable starting from that node. The memoization helps in storing previously computed answers to avoid redundant calculations.

Complexity

Time Complexity: O(n + e), where n is the number of people and e is the number of relationships. Each node and edge is processed once.
Space Complexity: O(n + e), to store the graph and the answer array.

Try this approach in the editor

Approach 2: Topological Sort Based Approach

This approach involves using topological sorting to process the nodes in an order where each node processes its neighbors only after it has been considered. This sorts the nodes such that for any richer pair a -> b, 'a' appears before 'b'. We then traverse the graph to determine the quietest person for each node.

Python

from collections import defaultdict, deque

def loudAndRich(richer, quiet):
    n = len(quiet)
    indegree = [0] * n
    graph = defaultdict(list)
    for u, v in richer:
        graph[u].append(v)
        indegree[v] += 1
    order = deque([i for i in range(n) if indegree[i] == 0])
    answer = list(range(n))
    while order:
        u = order.popleft()
        for v in graph[u]:
            if quiet[answer[u]] < quiet[answer[v]]:
                answer[v] = answer[u]
            indegree[v] -= 1
            if indegree[v] == 0:
                order.append(v)
    return answer

We first construct a graph and calculate in-degrees for each node. Using a queue (BFS approach), nodes with zero in-degree are processed first, ensuring an order where a richer person is processed before the one richer than them. For each node, update the answer to maintain the quietest reachable person using the quiet array.

Complexity

Time Complexity: O(n + e), as each node and edge is processed.
Space Complexity: O(n + e), due to storing the graph and in-degrees.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function loudAndRich(richer: number[][], quiet: number[]): number[] {
    const n = quiet.length;
    const g: number[][] = new Array(n).fill(0).map(() => []);
    for (const [a, b] of richer) {
        g[b].push(a);
    }
    const ans: number[] = new Array(n).fill(-1);
    const dfs = (i: number) => {
        if (ans[i] != -1) {
            return ans;
        }
        ans[i] = i;
        for (const j of g[i]) {
            dfs(j);
            if (quiet[ans[j]] < quiet[ans[i]]) {
                ans[i] = ans[j];
            }
        }
    };
    for (let i = 0; i < n; ++i) {
        dfs(i);
    }
    return ans;
}

func loudAndRich(richer [][]int, quiet []int) []int {
	n := len(quiet)
	g := make([][]int, n)
	ans := make([]int, n)
	for i := range g {
		ans[i] = -1
	}
	for _, r := range richer {
		a, b := r[0], r[1]
		g[b] = append(g[b], a)
	}
	var dfs func(int)
	dfs = func(i int) {
		if ans[i] != -1 {
			return
		}
		ans[i] = i
		for _, j := range g[i] {
			dfs(j)
			if quiet[ans[j]] < quiet[ans[i]] {
				ans[i] = ans[j]
			}
		}
	}
	for i := range ans {
		dfs(i)
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Graph Representation and DFS with Memoization	Time Complexity: O(n + e), where n is the number of people and e is the number of relationships. Each node and edge is processed once. Space Complexity: O(n + e), to store the graph and the answer array.
Topological Sort Based Approach	Time Complexity: O(n + e), as each node and edge is processed. Space Complexity: O(n + e), due to storing the graph and in-degrees.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Graph DFS with Memoization	O(n + m)	O(n + m)	General case. Best when exploring richer relationships recursively with caching.
Topological Sort Propagation	O(n + m)	O(n + m)	Useful when modeling the problem as dependency flow in a DAG.

Frequently asked questions

Is Loud and Rich easy or hard?

Loud and Rich is rated Medium difficulty on LeetCode. The challenge is recognizing that the richer relationships form a directed graph and that results can be reused with memoization. Once modeled correctly, the implementation is straightforward.

How to solve Loud and Rich in O(n)?

Model the richer relationships as a graph and compute the quietest reachable person for each node. Using DFS with memoization ensures each node's result is cached after the first computation. Since each edge is visited once, the total complexity becomes O(n + m).

What is the best approach for Loud and Rich?

DFS with memoization on the graph is the most common solution. Build edges from each person to people richer than them and recursively search for the quietest reachable person. Memoization ensures each node is processed once, giving O(n + m) time complexity.

What data structure is used in Loud and Rich?

The core data structure is an adjacency list representing a directed graph. The solution also uses arrays for memoization and quietness tracking. DFS recursion or a queue for topological sort is used to traverse the graph efficiently.

What is the time complexity of Loud and Rich?

Both optimal approaches run in O(n + m) time where n is the number of people and m is the number of richer relationships. Each node and edge in the graph is processed at most once. Space complexity is also O(n + m) for the adjacency list and memoization storage.

Loud and Rich Python or Java solution approach

Both Python and Java implementations follow the same logic: build a graph from poorer to richer nodes, run DFS with memoization, and return the quietest reachable person for each index. The algorithmic complexity remains O(n + m) regardless of language.

Is Loud and Rich asked at Google, Amazon, or Meta?

Graph traversal problems like Loud and Rich frequently appear in interviews at companies such as Amazon, Google, and Meta. Variants involving dependency graphs, memoized DFS, or topological ordering are common in system-style algorithm questions.

Loud and Rich solution and explanation

The problem

Approach overview

Approach 1: Graph Representation and DFS with Memoization

Approach 2: Topological Sort Based Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Loud and Rich solution and explanation

The problem

Approach overview

Approach 1: Graph Representation and DFS with Memoization

Approach 2: Topological Sort Based Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems