Sponsored
Sponsored
This approach involves representing the problem as a directed graph, where each edge indicates that one person is richer than another. We perform a Depth-First Search (DFS) from each node to find the quietest person that can potentially reach the given node using memoization to optimize the search process.
Time Complexity: O(n + e), where n is the number of people and e is the number of relationships. Each node and edge is processed once.
Space Complexity: O(n + e), to store the graph and the answer array.
1var loudAndRich = function(richer, quiet) {
2 let n = quiet.length;
3 let graph = Array.from({length: n}, () => []);
4 for (let [u, v] of richer) {
5 graph[v].push(u);
6 }
7
8 let answer = Array(n).fill(-1);
9
10 const dfs = (node) => {
11 if (answer[node] !== -1) return answer[node];
12 answer[node] = node;
13 for (let nei of graph[node]) {
14 let cand = dfs(nei);
15 if (quiet[cand] < quiet[answer[node]]) {
16 answer[node] = cand;
17 }
18 }
19 return answer[node];
20 };
21
22 for (let i = 0; i < n; i++) {
23 dfs(i);
24 }
25 return answer;
26};The solution is similar to the Python version. A graph is built to represent richer relationships, and Depth-First Search is applied using recursion to determine the quietest person reachable from each node. The memoization technique stores previously computed results for efficiency.
This approach involves using topological sorting to process the nodes in an order where each node processes its neighbors only after it has been considered. This sorts the nodes such that for any richer pair a -> b, 'a' appears before 'b'. We then traverse the graph to determine the quietest person for each node.
Time Complexity: O(n + e), as each node and edge is processed.
Space Complexity: O(n + e), due to storing the graph and in-degrees.
1from collections import defaultdict, deque
2
3def loudAndRich(richer, quiet):We first construct a graph and calculate in-degrees for each node. Using a queue (BFS approach), nodes with zero in-degree are processed first, ensuring an order where a richer person is processed before the one richer than them. For each node, update the answer to maintain the quietest reachable person using the quiet array.