Loud and Rich
Asked at Flipkart
Problem
Loud and Rich gives you pairs saying who is richer than whom, plus each person's quietness, and asks, for every person x, which person among those with at least as much money as x is the quietest. It is a DAG problem: propagate "quietest richer-or-equal person" along the richer-than edges with memoized DFS.
Asked At
| Company | Difficulty | |
|---|---|---|
| Flipkart | Medium | View all Flipkart questions → |
How to Think About It
Build a graph where each person points to the people who are directly richer than them. Because the "richer" relation is consistent, this graph is a DAG.
For person x, the candidates are x plus everyone reachable from x in that graph.
Key insight: answer[x] is the quieter of x itself and answer[y] for each direct richer neighbor y. That is a recursive definition — memoize it so each person is solved once.
Walkthrough: if 1 is richer than 0 and 2 is richer than 1, then answer[0] compares 0 with answer[1], which compares 1 with answer[2]. The quietest of the three wins.
Alternative: topological sort from richest to poorest and push answers downward — same complexity.
Optimal Approach
Step 1: Build richer_than[x] = list of people directly richer than x.
Step 2: answer = [-1] * n.
Step 3: dfs(x):
If answer[x] != -1, return it.
best = x.
For each y in richer_than[x]: cand = dfs(y); if quiet[cand] < quiet[best], best = cand.
answer[x] = best; return it.
Step 4: Call dfs for every person.
Time: O(n + e). Space: O(n + e).
What Trips People Up in Real Interviews
Pointing edges the wrong way. For each x you need the people richer than x, so edges go from poorer to richer.
Running a fresh DFS/BFS from every person without memoization — that is O(n * (n + e)).
Returning the quietness value instead of the person's index.
Forgetting that x itself is a candidate (people with equal money include x).
Solution Code
def loudAndRich(richer, quiet):
n = len(quiet)
richer_than = [[] for _ in range(n)]
for a, b in richer:
richer_than[b].append(a)
answer = [-1] * n
def dfs(x):
if answer[x] != -1:
return answer[x]
best = x
for y in richer_than[x]:
cand = dfs(y)
if quiet[cand] < quiet[best]:
best = cand
answer[x] = best
return best
for x in range(n):
dfs(x)
return answerFrequently Asked Questions
What is the Loud and Rich problem?
Loud and Rich gives you pairs saying who is richer than whom, plus each person's quietness, and asks, for every person `x`, which person among those with at least as much money as `x` is the quietest. It is a DAG problem: propagate "quietest richer-or-equal person" along the richer-than edges with memoized DFS.
How do you solve Loud and Rich?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Loud and Rich?
Loud and Rich is asked at Flipkart. It is a medium difficulty problem.
What are common mistakes on Loud and Rich?
- Pointing edges the wrong way. For each `x` you need the people richer than `x`, so edges go from poorer to richer.
- Running a fresh DFS/BFS from every person without memoization — that is `O(n * (n + e))`.
- Returning the quietness value instead of the person's index.
- Forgetting that `x` itself is a candidate (people with equal money include `x`).