In this guide, you will get 851. Loud and Rich LeetCode Solution with the best time and space complexity. The solution to Loud and Rich problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
There is a group of n people labeled from 0 to n – 1 where each person has a different amount of money and a different level of quietness.
You are given an array richer where richer[i] = [ai, bi] indicates that ai has more money than bi and an integer array quiet where quiet[i] is the quietness of the ith person. All the given data in richer are logically correct (i.e., the data will not lead you to a situation where x is richer than y and y is richer than x at the same time).
Return an integer array answer where answer[x] = y if y is the least quiet person (that is, the person y with the smallest value of quiet[y]) among all people who definitely have equal to or more money than the person x.
Example 1:
Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation:
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but it is not clear if they have more money than person 0.
answer[7] = 7.
Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7.
The other answers can be filled out with similar reasoning.
n == quiet.length
1 <= n <= 500
0 <= quiet[i] < n
All the values of quiet are unique.
0 <= richer.length <= n * (n – 1) / 2
0 <= ai, bi < n
ai != bi
All the pairs of richer are unique.
The observations in richer are all logically consistent.
Complexity Analysis
Time Complexity: O(|V| + |E|), where |V| = |\texttt{quiet}| and |E| = |\texttt{richer}|
Space Complexity: O(|V| + |E|)
851. Loud and Rich LeetCode Solution in C++
class Solution {
public:
vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
const int n = quiet.size();
vector<int> ans(n, -1);
vector<vector<int>> graph(n);
for (const vector<int>& r : richer) {
const int u = r[1];
const int v = r[0];
graph[u].push_back(v);
}
for (int i = 0; i < n; ++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];
}
}; /* code provided by PROGIEZ */
851. Loud and Rich LeetCode Solution in Java
class Solution {
public int[] loudAndRich(int[][] richer, int[] quiet) {
final int n = quiet.length;
int[] ans = new int[n];
List<Integer>[] graph = new List[n];
Arrays.fill(ans, -1);
for (int i = 0; i < n; ++i)
graph[i] = new ArrayList<>();
for (int[] r : richer) {
final int u = r[1];
final int v = r[0];
graph[u].add(v);
}
for (int i = 0; i < n; ++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];
}
} // code provided by PROGIEZ
851. Loud and Rich LeetCode Solution in Python
class Solution:
def loudAndRich(self, richer: list[list[int]], quiet: list[int]) -> list[int]:
graph = [[] for _ in range(len(quiet))]
for v, u in richer:
graph[u].append(v)
@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))) # code by PROGIEZ
