Loud and Rich

Medium
938.

Loud and Rich

Loud and Rich is a medium coding problem on arrays, depth-first search and graph, asked in Amazon, Google and Bloomberg interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} richer
 * @param {number[]} quiet
 * @return {number[]}
 */
var loudAndRich = function(richer, quiet) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Loud and Rich — Solution in Python, Java & C++

Loud and Rich solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Loud and Rich is a medium coding problem on arrays, depth-first search and graph, asked in Amazon, Google and Bloomberg interviews.

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.

Hints for Loud and Rich

  1. Hint 1

    Draw an edge from each richer person to each poorer one. Consistency means the graph is acyclic.

  2. Hint 2

    A person's answer is the best among their own quietness and the answers of everyone richer than them.

  3. Hint 3

    Process people in topological order, richest first, pushing answers downhill.

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

  1. Build the edges richer → poorer and count in-degrees.
  2. Start every answer as the person themselves and queue the in-degree-zero people.
  3. When popping u, offer ans[u] to each poorer neighbour v, keeping whichever is quieter.
  4. 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

Java

public static int[] loudAndRich(int[][] richer, int[] quiet) {
    int n = quiet.length;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] r : richer) {
        adj.get(r[0]).add(r[1]);
        indeg[r[1]]++;
    }
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) ans[i] = i;
    int[] q = new int[n];
    int head = 0, tail = 0;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q[tail++] = i;
    while (head < tail) {
        int u = q[head++];
        for (int v : adj.get(u)) {
            if (quiet[ans[u]] < quiet[ans[v]]) ans[v] = ans[u];
            if (--indeg[v] == 0) q[tail++] = v;
        }
    }
    return ans;
}

C++

vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
    int n = (int) quiet.size();
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0), ans(n);
    for (int i = 0; i < n; i++) ans[i] = i;
    for (auto& r : richer) {
        adj[r[0]].push_back(r[1]);
        indeg[r[1]]++;
    }
    vector<int> q;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push_back(i);
    for (size_t head = 0; head < q.size(); head++) {
        int u = q[head];
        for (int v : adj[u]) {
            if (quiet[ans[u]] < quiet[ans[v]]) ans[v] = ans[u];
            if (--indeg[v] == 0) q.push_back(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)