Problem Breakdown
We are given N people with unique labels from 0 to N-1. We have two pieces of information:
- Richer Relations: A list
richer, where each pair[x, y]indicates personxhas strictly more money than persony. This defines a directed relationship . Since “more money” is transitive (if A > B and B > C, then A > C) and consistent, this structure forms a Directed Acyclic Graph (DAG). - Quietness: An array
quietwherequiet[i]represents the quietness level of personi.
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
icontains the label of the least quiet person among those richer or equal toi.
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 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 tou. - Optimization: We can reverse the graph edges so they point from Poorer 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
- Graph Construction: The input
richergives edges[x, y]meaning has more money than . To find people richer than a specific person efficiently during traversal, it’s easier to build an adjacency list where we add edgey -> x. This way, starting from any node and traversing forward takes us directly to all strictly richer nodes. - 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)personin our reversed graph. - Recursion Logic:
- If we have already computed the result for
person, return it immediately. - Otherwise, initialize a candidate as
personthemselves (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.
- If we have already computed the result for
- Finalization: Store the result for each node before returning it, then populate the
answerarray by calling this function for every person from to .
Complexity Analysis
- Time Complexity: where is the number of pairs in
richer. We build the graph in . 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 (, ), this fits well within limits (roughly operations max). - Space Complexity: 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]: