Loud and Rich
01 · Problem
There are n people labelled 0 to n - 1. Each person has a distinct amount of money and a distinct level of quietness.
You are given richer, where richer[i] = [a, b] means person a has strictly more money than person b. This list is only partial information, but it is logically consistent (it never implies someone is richer than themselves). You are also given quiet, where quiet[i] is person i's quietness; all values in quiet are distinct and a smaller value means quieter.
Return an array answer of length n where answer[x] is the person y with the smallest quiet[y] among all people who are known to have at least as much money as x. Person x always counts (they have as much money as themselves). "Known" means derivable by following richer pairs, directly or through a chain.
Because quietness values are distinct, each answer[x] is unique.
02 · Examples
richer = [[0,1],[1,2]], quiet = [2,0,1]
[0,1,1]
Wealth order is 0 > 1 > 2. For person 0, only person 0 qualifies, so the answer is 0. For person 1, candidates are {0, 1}; person 1 is quietest (0). For person 2, candidates are {0, 1, 2}; person 1 is still quietest.
richer = [], quiet = [0]
[0]
There is only one person and they are trivially the answer for themselves.
richer = [[2,0],[2,1],[3,2]], quiet = [1,3,2,4]
[0,2,2,3]
Person 0 is known to be poorer than 2 and 3, so candidates are {0, 2, 3} with quietness 1, 2, 4 -> person 0. Person 1: {1, 2, 3} with quietness 3, 2, 4 -> person 2. Person 2: {2, 3} -> person 2. Person 3: only themselves.
03 · Constraints
- 01n == quiet.length
- 021 <= n <= 500
- 030 <= quiet[i] < n and all quiet[i] are distinct
- 040 <= richer.length <= n * (n - 1) / 2, all pairs distinct, a != b
- 05The richer relation contains no cycles
04 · Optimal complexity
- Time
- O(n + m)
- Space
- O(n + m)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.