Loud and Rich
Explanation & Solution
Description
There is a group of n people labeled from 0 to n - 1, each with 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 person a_i has strictly more money than person b_i.
You are also given an integer array quiet where quiet[i] is the quietness of the i-th person. All values in quiet are unique.
For each person x, find the quietest person (the person y with the smallest quiet[y]) among all people who are at least as rich as person x (including person x themselves).
Return an integer array answer where answer[x] = y.
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]
Output: [5,5,2,5,4,5,6,7]
Explanation:
- answer[0] = 5: Among people richer than or equal to person 0 (persons 0, 1, 2, 3, 4, 5, 6), person 5 has quietness 1 which is the minimum.
- answer[7] = 7: No one is richer than person 7, so the answer is person 7 themselves with quietness 0.
Example 2
Input: richer = [[0,1],[1,2]], quiet = [0,1,2]
Output: [0,0,0]
Explanation: Person 0 is the richest and also the quietest. Everyone has person 0 as at least as rich, so all answers are 0.
Constraints
- n == quiet.length
- 1 <= n <= 500
- 0 <= quiet[i] < n
- All values of quiet are unique.
- 0 <= richer.length <= n * (n - 1) / 2
- 0 <= a_i, b_i < n
- a_i != b_i
- No two entries in richer are the same.
- The richer relations can be represented as a DAG.
Approach
Topological Sort pattern
1. Build the Richer Graph
- Create a directed graph where each edge goes from a richer person to a poorer person.
- Compute the in-degree of each node (how many people are directly richer).
2. Initialize Answers
- Set answer[i] = i for every person. Initially, the quietest person at least as rich as person i is person i themselves.
3. Topological Sort with Propagation
- Start BFS from all nodes with in-degree 0 (the richest people — no one is richer than them).
- When processing a node, for each poorer neighbor:
- Compare the quietness of the current best answer for the node vs. the neighbor's current best.
- If the node's best is quieter, update the neighbor's answer.
- Decrement in-degree; if it hits 0, add the neighbor to the queue.
4. Return the Answer Array
- After processing all nodes, answer[x] holds the person with minimum quietness among everyone at least as rich as x.
Key Insight
- By processing in topological order (richest first), when we visit a person, we have already determined the quietest person among all people richer than them. We simply propagate this minimum down the "richer-than" edges. Each edge is visited once, giving us O(n + E) time complexity.