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

1
2
3
4
5
6
7
8
9

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 is not 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.

Example 2

1
2

Input: richer = [], quiet = [0]
Output: [0]

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

  1. Build a graph where an edge from u to v means u is richer than v.
  2. For each person, perform DFS to find the quietest person among themselves and all richer people.
  3. Use memoization to avoid redundant calculations.
  4. For each node, compare their quietness with the quietest among their richer neighbors.
  5. Return the answer array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
        int n = quiet.size();
        vector<vector<int>> g(n);
        for (auto& e : richer) g[e[1]].push_back(e[0]);
        vector<int> ans(n, -1);
        function<int(int)> dfs = [&](int u) {
            if (ans[u] != -1) return ans[u];
            ans[u] = u;
            for (int v : g[u]) {
                int cand = dfs(v);
                if (quiet[cand] < quiet[ans[u]]) ans[u] = cand;
            }
            return ans[u];
        };
        for (int i = 0; i < n; ++i) dfs(i);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func loudAndRich(richer [][]int, quiet []int) []int {
    n := len(quiet)
    g := make([][]int, n)
    for _, e := range richer {
        g[e[1]] = append(g[e[1]], e[0])
    }
    ans := make([]int, n)
    for i := range ans {
        ans[i] = -1
    }
    var dfs func(int) int
    dfs = func(u int) int {
        if ans[u] != -1 {
            return ans[u]
        }
        ans[u] = u
        for _, v := range g[u] {
            cand := dfs(v)
            if quiet[cand] < quiet[ans[u]] {
                ans[u] = cand
            }
        }
        return ans[u]
    }
    for i := 0; i < n; i++ {
        dfs(i)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int[] e : richer) g[e[1]].add(e[0]);
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        for (int i = 0; i < n; i++) dfs(i, g, quiet, ans);
        return ans;
    }
    int dfs(int u, List<Integer>[] g, int[] quiet, int[] ans) {
        if (ans[u] != -1) return ans[u];
        ans[u] = u;
        for (int v : g[u]) {
            int cand = dfs(v, g, quiet, ans);
            if (quiet[cand] < quiet[ans[u]]) ans[u] = cand;
        }
        return ans[u];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun loudAndRich(richer: Array<IntArray>, quiet: IntArray): IntArray {
        val n = quiet.size
        val g = Array(n) { mutableListOf<Int>() }
        for (e in richer) g[e[1]].add(e[0])
        val ans = IntArray(n) { -1 }
        fun dfs(u: Int): Int {
            if (ans[u] != -1) return ans[u]
            ans[u] = u
            for (v in g[u]) {
                val cand = dfs(v)
                if (quiet[cand] < quiet[ans[u]]) ans[u] = cand
            }
            return ans[u]
        }
        for (i in 0 until n) dfs(i)
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def loudAndRich(self, richer: list[list[int]], quiet: list[int]) -> list[int]:
        n = len(quiet)
        g = [[] for _ in range(n)]
        for u, v in richer:
            g[v].append(u)
        ans = [-1] * n
        def dfs(u: int) -> int:
            if ans[u] != -1:
                return ans[u]
            ans[u] = u
            for v in g[u]:
                cand = dfs(v)
                if quiet[cand] < quiet[ans[u]]:
                    ans[u] = cand
            return ans[u]
        for i in range(n):
            dfs(i)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

impl Solution {
    pub fn loud_and_rich(richer: Vec<Vec<i32>>, quiet: Vec<i32>) -> Vec<i32> {
        let n = quiet.len();
        let mut g = vec![vec![]; n];
        for e in richer.iter() {
            g[e[1] as usize].push(e[0] as usize);
        }
        let mut ans = vec![-1; n];
        fn dfs(u: usize, g: &Vec<Vec<usize>>, quiet: &Vec<i32>, ans: &mut Vec<i32>) -> i32 {
            if ans[u] != -1 {
                return ans[u];
            }
            ans[u] = u as i32;
            for &v in &g[u] {
                let cand = dfs(v, g, quiet, ans);
                if quiet[cand as usize] < quiet[ans[u] as usize] {
                    ans[u] = cand;
                }
            }
            ans[u]
        }
        for i in 0..n {
            dfs(i, &g, &quiet, &mut ans);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    loudAndRich(richer: number[][], quiet: number[]): number[] {
        const n = quiet.length;
        const g: number[][] = Array.from({length: n}, () => []);
        for (const [u, v] of richer) g[v].push(u);
        const ans = Array(n).fill(-1);
        const dfs = (u: number): number => {
            if (ans[u] !== -1) return ans[u];
            ans[u] = u;
            for (const v of g[u]) {
                const cand = dfs(v);
                if (quiet[cand] < quiet[ans[u]]) ans[u] = cand;
            }
            return ans[u];
        };
        for (let i = 0; i < n; ++i) dfs(i);
        return ans;
    }
}

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.