#851
Loud and Rich
specialist · 715 · lc medium +30 · verified · 63.2% accepted · 1,489 likes · top 65%
Description
There are n people labeled 0 through n - 1. Each person has a unique wealth level and a quietness rating.
You are given an array richer where richer[i] = [ai, bi] means person ai is wealthier than person bi. The data is logically consistent (no cyclic wealth relations). You are also given an integer array quiet where quiet[i] is the quietness of person i.
Return an integer array answer where answer[x] = y means that y is the person with the lowest quietness value among all people who are definitively at least as wealthy as 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]
Code
1
2
3