Skip to main content
Talentd

Loud and Rich - Solution & Explanation

MediumArrayDepth-First SearchGraphTopological Sort11 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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] = [ai, bi] indicates that ai has more money than bi and an integer array quiet where quiet[i] is the quietness of the ith 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 <= ai, bi < n
  • ai != bi
  • 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.

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.

Code

PythonJavaScriptJavaC++C#

Python

JavaScript

Java

C++

C#

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.

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.

Code

Python

Python

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Graph DFS with MemoizationO(n + m)O(n + m)General case. Best when exploring richer relationships recursively with caching.
Topological Sort PropagationO(n + m)O(n + m)Useful when modeling the problem as dependency flow in a DAG.

Video Solution

Leetcode 851 | Loud and Rich | DFS | Graph • Hellgeek Arena • 7,178 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Loud and Rich with our built-in code editor and test cases.

Practice on FleetCode
Previous

Build a Matrix With Conditions