Loud and Rich
Medium · Graphs · Array · Depth-First Search · Graph · Topological Sort
Problem
There are n people labelled 0 to n - 1. Each richer[i] = [a, b] states that person a has strictly more money than person b. The facts are consistent: nobody ends up richer than themselves through a chain of them.
quiet[i] is how quiet person i is, and all values are different (smaller means quieter).
Return a list answer where answer[x] is the person y with the smallest quiet[y] among everyone known to have at least as much money as x: x itself, plus anyone a chain of facts leads from down to x.
Examples
Input: richer = [[1,0],[2,1],[3,0]], quiet = [4,2,3,1] Output: [3,1,2,3]
Everyone else is above person 0, and person 3 is the quietest. Person 1 has only person 2 above, who is louder, so 1 keeps itself.
Input: richer = [], quiet = [1,0] Output: [0,1]
With no facts, each person only has themselves.
Input: richer = [[0,1],[1,2]], quiet = [0,2,1] Output: [0,0,0]
Person 0 is above everyone and is the quietest, so every answer is 0.
Constraints
- n == len(quiet)
- 1 <= n <= 500
- quiet is a permutation of 0..n-1
- 0 <= len(richer) <= n * (n - 1) / 2
- richer[i] == [a, b] with a != b, all pairs distinct
- The facts never contradict each other
Approaches
- Search upward from every person — time O(n · (n + m)), space O(n + m)
Follow-up
The answer for a person reuses the answers of the people directly above, which only works because "quietest" combines cleanly: the best of the bests is the best. A count of everyone richer does not combine that way (two paths reach the same person), which the first use case shows. The second turns the question around and looks down the order instead.
Related problems
Start free on Cariara · Coding problems · System design studio
