MediumArrayDepth-First SearchGraphTopological SortUpdated Sep 2026

851. Loud and Rich

Asked at Flipkart

Difficulty

Medium

Time

O(n + e)

Space

O(n + e)

Pattern

Array

Companies

1

Problem

There are n people, numbered 0 to n-1. Each person has a different amount of money and a different quietness level. You are given richer, a list of pairs where richer[i] = [a, b] means person a has more money than person b. You are also given quiet, where quiet[i] is the quietness of person i — a smaller number means a quieter person.

For every person x, look at all people who definitely have at least as much money as x (this always includes x itself). Among them, find the quietest one. Return an array answer where answer[x] is that quietest person's index.

Note that "at least as much money" means reachable through the richer pairs. If the data does not prove that person y has more money than x, then y is not a candidate for answer[x], even if y is very quiet. The given pairs are always logically consistent, so no cycles can appear.

Who is richer, and who is quietest?

richer pairsab10213137435363Each row means: a has more money than bquiet3254617001234567Person 5 has quiet 1, person 7 has quiet 0 — the smallest of all
Arrows point from a richer person to a poorer person. For each person we want the quietest person that can reach them.

Constraints

  • ●n == quiet.length
  • ●1 <= n <= 500
  • ●0 <= quiet[i] < n
  • ●All values of quiet are unique.
  • ●0 <= richer.length <= n * (n - 1) / 2
  • ●0 <= ai, bi < n
  • ●ai != bi
  • ●All pairs in richer are unique.

Examples

Example 1
Inputricher = [[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]
WhyFor person 0: 1 is richer than 0, 2 is richer than 1, and 3 is richer than 1, so 5 (richer than 3) is also richer than 0. Person 7 is quieter than 5, but nothing proves 7 is richer than 0, so 5 wins. For person 7: nobody is proven richer than 7, so the only candidate is 7 itself.
Example 2
Inputricher = [], quiet = [0]
Output[0]
WhyThere is only one person and no money relations, so person 0 is the only candidate for themselves.

Asked At

1 companies
CompanyDifficulty
FlipkartMediumView all Flipkart questions →

How to Think About It

1

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.

2

For person x, the candidates are x plus everyone reachable from x in that graph.

3

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.

4

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.

5

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).

Memoized DFS up the richer chain

build richer_than[x] = people directly richedfs(x): best = xfor each richer y: cand = dfs(y)keep cand if quiet[cand] < quiet[best]memoize answer[x] = bestThe recursion walks up the money chain and caches each resultanswer5525456701234567answer[0] = 5 and answer[7] = 7 — the quietest reachable person foreachanswer[x] = argmin quiet over {x} ∪ reachable(x)dfs(x) = best of x and dfs(y) for richer y
Each person asks their direct richer neighbors for their answer, then keeps the quietest candidate.
ComplexityTime O(n + e)Space O(n + e)n is the number of people and e is the number of richer pairs; each person and each edge is processed once thanks to memoization.

What Trips People Up in Real Interviews

1

Pointing edges the wrong way. For each x you need the people richer than x, so edges go from poorer to richer.

2

Running a fresh DFS/BFS from every person without memoization — that is O(n * (n + e)).

3

Returning the quietness value instead of the person's index.

4

Forgetting that x itself is a candidate (people with equal money include x).

Solution Code

O(n + e) time
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 answer

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n + e) time and O(n + e) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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`).