In a group of N people (labelled `0, 1, 2, ..., N-1`

), each person has different amounts of money, and different levels of quietness.

For convenience, we’ll call the person with label `x`

, simply “person `x`

“.

We’ll say that `richer[i] = [x, y]`

if person `x`

definitely has more money than person `y`

. Note that `richer`

may only be a subset of valid observations.

Also, we’ll say `quiet[x] = q`

if person x has quietness `q`

.

Now, return `answer`

, where `answer[x] = y`

if `y`

is the least quiet person (that is, the person `y`

with the smallest value of `quiet[y]`

), among all people who definitely have equal to or more money than 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 isn't 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.

**Note:**

`1 <= quiet.length = N <= 500`

`0 <= quiet[i] < N`

, all`quiet[i]`

are different.`0 <= richer.length <= N * (N-1) / 2`

`0 <= richer[i][j] < N`

`richer[i][0] != richer[i][1]`

`richer[i]`

‘s are all different.- The observations in
`richer`

are all logically consistent.

**Solution: DFS + Memoization**

For person i , remember the quietest person who is richer than person i.

Time complexity: O(n^2)

Space complexity: O(n)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua, running time: 108 ms, 31.6 MB class Solution { public: vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) { const int n = quiet.size(); vector<vector<int>> g(n); for (const auto& r : richer) g[r[1]].push_back(r[0]); vector<int> ans(n, -1); function<void(int)> dfs = [&](int i) { if (ans[i] != -1) return; ans[i] = i; for (int j : g[i]) { dfs(j); if (quiet[ans[j]] < quiet[ans[i]]) ans[i] = ans[j]; } }; for (int i = 0; i < n; ++i) dfs(i); return ans; } }; |