Problem
There is a group of n
people labeled from 0
to n - 1
where each person has a different amount of money and a different level of quietness.
You are given an array richer
where richer[i] = [ai, bi]
indicates that
ai
has more money than bi
and an integer array quiet
where quiet[i]
is the quietness of the ith
person. All the given data in richer are
logically correct (i.e., the data will not lead you to a situation where
x
is richer than y
and y
is richer than x
at the same time).
Return an integer arrayanswer
whereanswer[x] = y
ify
is the least quiet person (that is, the persony
with the smallest value ofquiet[y]
) among all people who definitely have equal to or more money than the personx
.
Examples
Example 1
|
|
Example 2
|
|
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 <= ai, bi < n
ai != bi
- All the pairs of
richer
are unique. - The observations in
richer
are all logically consistent.
Solution
Method 1 – DFS with Memoization
Intuition
We want to find, for each person, the least quiet person among all who are at least as rich as them. We can model the richer relationships as a graph and use DFS with memoization to propagate the quietest person up the graph efficiently.
Approach
- Build a graph where an edge from
u
tov
meansu
is richer thanv
. - For each person, perform DFS to find the quietest person among themselves and all richer people.
- Use memoization to avoid redundant calculations.
- For each node, compare their quietness with the quietest among their richer neighbors.
- Return the answer array.
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n + m)
, where n is the number of people and m is the number of richer relations, as each node and edge is visited once. - 🧺 Space complexity:
O(n + m)
, for the graph and memoization array.