Loud and Rich — Solution in Python, Java & C++
Loud and Rich solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Loud and Rich is a medium coding problem on arrays, depth-first search and graph, asked in Amazon, Google and Bloomberg interviews.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Graph, Topological Sort
- Asked at: Amazon, Google, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n people numbered 0 … n - 1. richer[i] = [a, b] means person a has more money than person b, and quiet[i] is how quiet person i is — all the quietness values are different.
Return an array where entry x is the person y who is the quietest among everybody with at least as much money as x (including x itself). The information in richer is logically consistent.
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: Person 0 is beaten on quietness by person 5, who is richer via 1 ← 3 ← 5.
Example 2
Input: richer = [], quiet = [0]
Output: [0]
Example 3
Input: richer = [[0,1]], quiet = [0,1]
Output: [0,0]
Explanation: Person 0 is both richer and quieter, so they answer for themselves and for person 1.
Constraints
n == quiet.length1 <= n <= 5000 <= quiet[i] < nAll the values of quiet are unique.0 <= richer.length <= n * (n - 1) / 20 <= richer[i][0], richer[i][1] < nricher[i][0] != richer[i][1]All the pairs of richer are unique.The observations in richer are all logically consistent.
Hints for Loud and Rich
Hint 1
Draw an edge from each richer person to each poorer one. Consistency means the graph is acyclic.
Hint 2
A person's answer is the best among their own quietness and the answers of everyone richer than them.
Hint 3
Process people in topological order, richest first, pushing answers downhill.
How to solve Loud and Rich
Orient each richer pair from the richer person to the poorer one. The answer for a person is the quietest among themselves and everyone upstream, so sweep the DAG in topological order and relax each edge forward.
Approach
- Build the edges richer → poorer and count in-degrees.
- Start every answer as the person themselves and queue the in-degree-zero people.
- When popping
u, offerans[u]to each poorer neighbourv, keeping whichever is quieter. - Decrement
v's in-degree and queue it when it reaches zero.
Why it works
Topological order is what makes one pass enough: a person is only popped after every richer person has already offered their answer, so ans[u] is final before it propagates. "At least as much money" is a transitive relation, and relaxing along single edges composes into exactly that closure without ever enumerating it.
Complexity
- Time —
O(n + m) - Space —
O(n + m)
Pitfalls
- Compare quietness values, but return the person, not the value.
- Everyone starts as their own answer; a person with nobody richer keeps it.
- Relaxing before a node's in-degree hits zero can propagate a half-finished answer.
Reference solution
Python
from typing import List
from collections import deque
def loudAndRich(richer: List[List[int]], quiet: List[int]) -> List[int]:
n = len(quiet)
adj = [[] for _ in range(n)]
indeg = [0] * n
for a, b in richer:
adj[a].append(b)
indeg[b] += 1
ans = list(range(n))
q = deque(i for i in range(n) if indeg[i] == 0)
while q:
u = q.popleft()
for v in adj[u]:
if quiet[ans[u]] < quiet[ans[v]]:
ans[v] = ans[u]
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return ansJava
public static int[] loudAndRich(int[][] richer, int[] quiet) {
int n = quiet.length;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] r : richer) {
adj.get(r[0]).add(r[1]);
indeg[r[1]]++;
}
int[] ans = new int[n];
for (int i = 0; i < n; i++) ans[i] = i;
int[] q = new int[n];
int head = 0, tail = 0;
for (int i = 0; i < n; i++) if (indeg[i] == 0) q[tail++] = i;
while (head < tail) {
int u = q[head++];
for (int v : adj.get(u)) {
if (quiet[ans[u]] < quiet[ans[v]]) ans[v] = ans[u];
if (--indeg[v] == 0) q[tail++] = v;
}
}
return ans;
}C++
vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
int n = (int) quiet.size();
vector<vector<int>> adj(n);
vector<int> indeg(n, 0), ans(n);
for (int i = 0; i < n; i++) ans[i] = i;
for (auto& r : richer) {
adj[r[0]].push_back(r[1]);
indeg[r[1]]++;
}
vector<int> q;
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push_back(i);
for (size_t head = 0; head < q.size(); head++) {
int u = q[head];
for (int v : adj[u]) {
if (quiet[ans[u]] < quiet[ans[v]]) ans[v] = ans[u];
if (--indeg[v] == 0) q.push_back(v);
}
}
return ans;
}JavaScript
var loudAndRich = function(richer, quiet) {
var n = quiet.length, i;
var adj = [], indeg = [], ans = [];
for (i = 0; i < n; i++) { adj.push([]); indeg.push(0); ans.push(i); }
for (i = 0; i < richer.length; i++) {
adj[richer[i][0]].push(richer[i][1]);
indeg[richer[i][1]]++;
}
var q = [];
for (i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
var head = 0;
while (head < q.length) {
var u = q[head++];
for (i = 0; i < adj[u].length; i++) {
var v = adj[u][i];
if (quiet[ans[u]] < quiet[ans[v]]) ans[v] = ans[u];
indeg[v]--;
if (indeg[v] === 0) q.push(v);
}
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Depth-First Search (DFS)