Loud and Rich
Problem Statement
There are n people labelled from 0 to n − 1. Each person has a different amount of money and a different quietness: quiet[i] is the quietness of person i, and no two people share a value. A lower quiet value means a quieter person.
richer[i] = [a, b] says that person a has more money than person b. The facts are consistent, so nobody is richer than themselves through a chain.
For each person x, find the quietest person among everyone we can prove has at least as much money as x. A person counts if a chain of richer pairs links them to x. Person x counts too. Return the answer for every person.
richer, a list of pairs [a, b] (a is richer than b), and quiet, the quietness of each person.
answer, one entry per person: the quietest person who is at least as rich as that person.
Person 5 is richer than 3, who is richer than 1, who is richer than 0. Person 5 is the quietest of everyone who is at least as rich as person 0, so answer[0] = 5. For person 7, the people proven to be at least as rich are 3, 4, 5, 6 and 7 themselves. Person 7 is the quietest of them, so answer[7] = 7.
There is only one person, so that person is the answer.
- • 1 ≤ n ≤ 500
- • quiet.length = n
- • 0 ≤ quiet[i] < n
- • All the values of quiet are unique.
- • 0 ≤ richer.length ≤ n · (n − 1) / 2
- • 0 ≤ aᵢ, bᵢ < n
- • aᵢ ≠ bᵢ
- • All the pairs of richer are unique.
- • The observations in richer are all logically consistent.
Pattern Recognition Clues
Recognising these key signals in the problem description immediately identifies the pattern:
Approach Complexity Ladder
For each x, search all the richer people and keep the quietest one
Each person's answer is the quietest of themselves and their richer neighbours' answers; compute each one once
For each person x, collect everyone who is richer than x, directly or through a chain. Start a BFS at x, follow the richer pairs upward, and keep the person with the smallest quiet value that you reach.
Recognition rule for this sub-pattern:
Unlock Complete Visual Walkthrough & Optimal C++
The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.
How this concept connects to System Design & C++ Systems
Top engineering interviews test whether you understand how algorithms like Topological Sort translate into production architectures and low-level memory mechanics.