Loud and Rich — Medium Problem & Solution

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…

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.length
1 <= n <= 500
0 <= quiet[i] < n
All the values of quiet are unique.
0 <= richer.length <= n * (n - 1) / 2
0 <= richer[i][0], richer[i][1] < n
richer[i][0] != richer[i][1]
All the pairs of richer are unique.
The observations in richer are all logically consistent.

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, offer ans[u] to each poorer neighbour v, 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue