LeetCode Solutions
851. Loud and Rich
Time: $O(|V| + |E|)$, where $|V| = |\texttt{quiet}|$ and $|E| = |\texttt{richer}|$ Space: $O(|V| + |E|)$
class Solution {
public:
vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
vector<int> ans(quiet.size(), -1);
vector<vector<int>> graph(quiet.size());
for (const vector<int>& e : richer)
graph[e[1]].push_back(e[0]);
for (int i = 0; i < graph.size(); ++i)
dfs(graph, i, quiet, ans);
return ans;
}
private:
int dfs(const vector<vector<int>>& graph, int u, const vector<int>& quiet,
vector<int>& ans) {
if (ans[u] != -1)
return ans[u];
ans[u] = u;
for (const int v : graph[u]) {
const int res = dfs(graph, v, quiet, ans);
if (quiet[res] < quiet[ans[u]])
ans[u] = res;
}
return ans[u];
}
};
class Solution {
public int[] loudAndRich(int[][] richer, int[] quiet) {
int[] ans = new int[quiet.length];
List<Integer>[] graph = new List[quiet.length];
Arrays.fill(ans, -1);
for (int i = 0; i < graph.length; ++i)
graph[i] = new ArrayList<>();
for (int[] e : richer)
graph[e[1]].add(e[0]);
for (int i = 0; i < graph.length; ++i)
dfs(graph, i, quiet, ans);
return ans;
}
private int dfs(List<Integer>[] graph, int u, int[] quiet, int[] ans) {
if (ans[u] != -1)
return ans[u];
ans[u] = u;
for (final int v : graph[u]) {
final int res = dfs(graph, v, quiet, ans);
if (quiet[res] < quiet[ans[u]])
ans[u] = res;
}
return ans[u];
}
}
class Solution:
def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
graph = [[] for _ in range(len(quiet))]
for u, v in richer:
graph[v].append(u)
@functools.lru_cache(None)
def dfs(u: int) -> int:
ans = u
for v in graph[u]:
res = dfs(v)
if quiet[res] < quiet[ans]:
ans = res
return ans
return map(dfs, range(len(graph)))