Statementâ–¼
You’re given a group of individuals where everyone has a specific amount of money and a different level of quietness. Additionally, you’re given an array richer
= quiet
.
Return an integer array res
, where res[i]
= y
. If y
has the lowest value in quiet[y]
among all individuals, who have equal or more money than the individual i
.
Constraints:
n= quiet.length
1≤ n ≤500 0≤ quiet[i]
< n All the values of
quiet
are unique.0≤ richer.length
≤n∗(n−1)/2 0≤ xi​ ,yi​ < n
xi​ î€ = yi​ All the pairs of
richer
are unique.The observations in
richer
are all logically consistent.
Solution
To solve this problem, we will use the topological sort to ensure we handle each individual only after all their dependencies (richer individuals) are processed. We will build a directed acyclic graph (DAG) from the richer
array because no individual can simultaneously be richer and poorer than another.
Here’s what a DAG would look like: