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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] LoudAndRich(int[][] richer, int[] quiet) {
6 int n = quiet.Length;
7 var graph = new Dictionary<int, List<int>>();
8 for (int i = 0; i < n; i++) {
9 graph[i] = new List<int>();
10 }
11 foreach (var pair in richer) {
12 graph[pair[1]].Add(pair[0]);
13 }
14
15 int[] answer = new int[n];
16 Array.Fill(answer, -1);
17
18 for (int i = 0; i < n; i++) {
19 Dfs(i, quiet, answer, graph);
20 }
21 return answer;
22 }
23
24 private int Dfs(int node, int[] quiet, int[] answer, Dictionary<int, List<int>> graph) {
25 if (answer[node] != -1) return answer[node];
26 answer[node] = node;
27 foreach (var nei in graph[node]) {
28 int cand = Dfs(nei, quiet, answer, graph);
29 if (quiet[cand] < quiet[answer[node]]) {
30 answer[node] = cand;
31 }
32 }
33 return answer[node];
34 }
35}The C# implementation utilizes a dictionary to maintain the adjacency list of the graph and a similar DFS strategy to determine the quietest friend. The recursion is assisted by caching the results in the answer array.
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.