Domain 2MediumMEDIUM

Loud and Rich

For each person, find the least quiet individual among themselves and all strictly richer people using memoized DFS on a wealth hierarchy graph.

Domain: medium•Updated: 2026-09-02
#DFS#Memoization#DAG#Graph

Problem Breakdown

We are given N people with unique labels from 0 to N-1. We have two pieces of information:

  1. Richer Relations: A list richer, where each pair [x, y] indicates person x has strictly more money than person y. This defines a directed relationship x→yx \to y. Since “more money” is transitive (if A > B and B > C, then A > C) and consistent, this structure forms a Directed Acyclic Graph (DAG).
  2. Quietness: An array quiet where quiet[i] represents the quietness level of person i.

Goal: For every person x, we need to find the person y who has the smallest quiet[y] value among all people who are definitely richer than or equal to x. Note that “equal” includes x themselves. The set of candidates for any node is its ancestors in this money hierarchy plus itself.

Inputs:

  • richer: List of [parent, child] pairs (money-wise).
  • quiet: Array mapping person ID to quietness value.

Outputs:

  • An array where index i contains the label of the least quiet person among those richer or equal to i.

Intuition

A brute-force approach would be: for each person i, traverse upwards through the “richer” graph (finding everyone who has more money) and track the minimum quietness found.

  • Complexity: In a dense DAG, traversing all paths from every node could lead to O(N⋅E)O(N \cdot E) or worse without memoization because we might re-traverse common subgraphs for different starting nodes.
  • Key Insight: The problem asks us to find the minimum value (quietness) over an entire set of ancestors in a DAG. This is a classic Dynamic Programming on Graphs scenario. Since money relations are consistent, once we compute the “least quiet person” for a specific node u, that result applies regardless of how many times we query it from different paths leading to u.
  • Optimization: We can reverse the graph edges so they point from Poorer →\to Richer. Then, running DFS/BFS on this reversed graph allows us to traverse all people richer than a given node efficiently. By caching (memoizing) the result for each person, we ensure every edge and node is processed exactly once across the entire execution.

Approach

  1. Graph Construction: The input richer gives edges [x, y] meaning xx has more money than yy. To find people richer than a specific person efficiently during traversal, it’s easier to build an adjacency list where we add edge y -> x. This way, starting from any node and traversing forward takes us directly to all strictly richer nodes.
  2. DFS with Memoization: We define a recursive function dfs(person) that returns the label of the least quiet person in the component reachable from (and including) person in our reversed graph.
  3. Recursion Logic:
    • If we have already computed the result for person, return it immediately.
    • Otherwise, initialize a candidate as person themselves (since they are equal to or richer than themselves).
    • Iterate through all neighbors in our reversed graph (people who are strictly richer). Recursively call DFS on them and update the minimum quietness found so far.
  4. Finalization: Store the result for each node before returning it, then populate the answer array by calling this function for every person from 00 to N−1N-1.

Complexity Analysis

  • Time Complexity: O(N+E)O(N + E) where EE is the number of pairs in richer. We build the graph in O(E)O(E). The DFS visits each node and edge at most once due to memoization. Thus, total time is linear with respect to input size. Given constraints (N≤500N \le 500, E≈N2/2E \approx N^2/2), this fits well within limits (roughly 10610^6 operations max).
  • Space Complexity: O(N+E)O(N + E) for the adjacency list and recursion stack/memoization array. The memoization ensures we don’t re-compute subtrees, keeping space proportional to graph size.

Solution

class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)
        
        # Build adjacency list where edge y->x means x is strictly richer than y.
        # This allows us to traverse from a person upwards towards wealthier people.
        adj = [[] for _ in range(n)]
        for r_x, r_y in richer:
            adj[r_y].append(r_x)
            
        # Memoization array stores the ID of the least quiet person found 
        # so far for each node to avoid recomputation. Initialize with -2 (sentinel).
        memo = [-2] * n
        
        def dfs(person):
            if memo[person] != -2:
                return memo[person]
            
            current_min_quiet_person = person
            
            # Traverse all people who are strictly richer than 'current' node.
            for neighbor in adj[person]:
                candidate = dfs(neighbor)
                
                # If the quietest person found via a richer path is quieter, update result.
                if quiet[candidate] < quiet[current_min_quiet_person]:
                    current_min_quiet_person = candidate
            
            memo[person] = current_min_quiet_person
            return current_min_quiet_person
        
        answer = [dfs(i) for i in range(n)]
        
        return answer

```python
class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)
        
        # Build adjacency list where edge y->x means x is strictly richer than y.
        adj = [[] for _ in range(n)]
        for r_x, r_y in richer:
            adj[r_y].append(r_x)
            
        # Memoization array stores the ID of the least quiet person found 
        # so far for each node to avoid recomputation. Initialize with -2 (sentinel).
        memo = [-2] * n
        
        def dfs(person):
            if memo[person] != -2:
                return memo[person]
            
            current_min_quiet_person = person
            
            # Traverse all people who are strictly richer than 'current' node.
            for neighbor in adj[person]:
                candidate = dfs(neighbor)
                
                # If the quietest person found via a richer path is quieter, update result.
                if quiet[candidate] < quiet[current_min_quiet_person]:
                    current_min_quiet_person = candidate
            
            memo[person] = current_min_quiet_person
            return current_min_quiet_person
        
        answer = [dfs(i) for i in range(n)]
        
        return answer

```python
class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)
        
        # Build adjacency list where edge y->x means x is strictly richer than y.
        adj = [[] for _ in range(n)]
        for r_x, r_y in richer:
            adj[r_y].append(r_x)
            
        # Memoization array stores the ID of the least quiet person found 
        # so far for each node to avoid recomputation. Initialize with -2 (sentinel).
        memo = [-2] * n
        
        def dfs(person):
            if memo[person] != -2:
                return memo[person]
            
            current_min_quiet_person = person
            
            # Traverse all people who are strictly richer than 'current' node.
            for neighbor in adj[person]:
                candidate = dfs(neighbor)
                
                # If the quietest person found via a richer path is quieter, update result.
                if quiet[candidate] < quiet[current_min_quiet_person]:
                    current_min_quiet_person = candidate
            
            memo[person] = current_min_quiet_person
            return current_min_quiet_person
        
        answer = [dfs(i) for i in range(n)]
        
        return answer

```python
class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)
        
        # Build adjacency list where edge y->x means x is strictly richer than y.
        adj = [[] for _ in range(n)]
        for r_x, r_y in richer:
            adj[r_y].append(r_x)
            
        # Memoization array stores the ID of the least quiet person found 
        # so far for each node to avoid recomputation. Initialize with -2 (sentinel).
        memo = [-2] * n
        
        def dfs(person):
            if memo[person] != -2:
                return memo[person]
            
            current_min_quiet_person = person
            
            # Traverse all people who are strictly richer than 'current' node.
            for neighbor in adj[person]: