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.
1import java.util.*;
2
3public int[] loudAndRich(int[][] richer, int[] quiet) {
4 Map<Integer, List<Integer>> graph = new HashMap<>();
5 for (int i = 0; i < quiet.length; i++) {
6 graph.put(i, new ArrayList<>());
7 }
8 for (int[] pair : richer) {
9 graph.get(pair[1]).add(pair[0]);
10 }
11 int[] answer = new int[quiet.length];
12 Arrays.fill(answer, -1);
13
14 for (int i = 0; i < quiet.length; i++) {
15 dfs(i, quiet, answer, graph);
16 }
17 return answer;
18}
19
20private int dfs(int node, int[] quiet, int[] answer, Map<Integer, List<Integer>> graph) {
21 if (answer[node] != -1) return answer[node];
22 answer[node] = node;
23 for (int nei : graph.get(node)) {
24 int cand = dfs(nei, quiet, answer, graph);
25 if (quiet[cand] < quiet[answer[node]]) {
26 answer[node] = cand;
27 }
28 }
29 return answer[node];
30}The Java implementation creates an adjacency list to represent the richer relationships as a directed graph. Each node performs a DFS to find the quietest reachable node. The result is cached for efficiency, reducing repeated calculations.
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.