Loud and Rich

Loud and Rich

What is this problem about?

The Loud and Rich problem presents a group of people, an array representing how much money they have relative to each other (richer where richer[i] = [A, B] means A has strictly more money than B), and a quiet array representing how quiet each person is. Your goal is to return an array where the i-th element is the person who is the quietest (has the lowest quiet value) among all people who are equal to or richer than person i.

Why is this asked in interviews?

This is a classic Graph problem that evaluates a candidate's ability to model relationships as a Directed Acyclic Graph (DAG) and traverse it efficiently. Interviewers ask it because it forces candidates to translate real-world relative comparisons ("A is richer than B") into directed edges, and then apply Memoized Depth-First Search (DFS) or Topological Sort to answer queries without redundant calculations.

Algorithmic pattern used

This problem is optimally solved using DFS with Memoization (or Topological Sort). First, build a directed graph where edges point from poorer people to richer people (i.e., B -> A). To find the quietest richer person for person X, you perform a DFS starting from X, exploring all richer neighbors. You memoize the result (the quietest person found for X) in an answer array so that if another person's DFS reaches X, it instantly returns the precalculated answer.

Example explanation

Imagine 3 people. quiet = [3, 2, 6]. (Person 1 is quietest, Person 2 is loudest). richer = [[0, 1], [1, 2]] (0 is richer than 1. 1 is richer than 2). Graph: 2 -> 1 -> 0.

• Let's find answer for 0: 0 has no richer neighbors. Quietest is themselves (Person 0). ans[0] = 0.
• Let's find answer for 1: 1 points to 0.
  • Compare 1's quietness (2) with 0's quietness (3). Person 1 is quieter. ans[1] = 1.
• Let's find answer for 2: 2 points to 1.
  • 1 already computed their best answer! ans[1] = 1.
  • Compare 2's quietness (6) with Person 1's quietness (2). Person 1 is quieter. ans[2] = 1. Result: [0, 1, 1].

Common mistakes candidates make

A very common mistake is building the graph in the wrong direction (Richer -> Poorer). If you do this, you cannot easily query "who is richer than me" by following outgoing edges. Another critical error is forgetting to memoize. Without an array caching the final results of the DFS, you will re-evaluate entire subgraphs repeatedly, leading to a Time Limit Exceeded error on large test cases.

Interview preparation tip

When dealing with the Loud and Rich interview pattern, or any problem involving "relative hierarchies" (like course prerequisites or dependency graphs), immediately think of a Directed Graph. Practice writing a clean DFS that returns a value and stores that value in a global cache or answer array before returning it. This single pattern solves a vast majority of DAG dependency problems.