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.
1#include <vector>
2#include <algorithm>
3#include <unordered_map>
4
5using namespace std;
6
7vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
8 int n = quiet.size();
9 unordered_map<int, vector<int>> graph;
10 for (auto& pair : richer) {
11 graph[pair[1]].push_back(pair[0]);
12 }
13 vector<int> answer(n, -1);
14
15 function<int(int)> dfs = [&](int node) {
16 if (answer[node] != -1) return answer[node];
17 answer[node] = node;
18 for (int nei : graph[node]) {
19 int cand = dfs(nei);
20 if (quiet[cand] < quiet[answer[node]]) {
21 answer[node] = cand;
22 }
23 }
24 return answer[node];
25 };
26
27 for (int i = 0; i < n; ++i) {
28 dfs(i);
29 }
30 return answer;
31}The C++ solution uses a map to record the graph structure and applies a similar DFS approach to find the quietest reachable person. This is achieved through a lambda function which is called recursively.
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.