Loud and Rich

medium graph dfs topological-sort

Problem

richer[i] = [a, b] means person a has more money than b. Given quiet[i] (the quietness of person i), return answer where answer[i] is the index of the quietest person among those with money >= person i.

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]

Person 0 ends up with quietest among richer-or-equal being person 5.

input

def loudAndRich(richer, quiet):
    n = len(quiet)
    g = [[] for _ in range(n)]
    for a, b in richer:
        g[b].append(a)
    ans = [-1] * n
    def dfs(u):
        if ans[u] != -1: return ans[u]
        ans[u] = u
        for v in g[u]:
            cand = dfs(v)
            if quiet[cand] < quiet[ans[u]]:
                ans[u] = cand
        return ans[u]
    for i in range(n): dfs(i)
    return ans

function loudAndRich(richer, quiet) {
  const n = quiet.length;
  const g = Array.from({length: n}, () => []);
  for (const [a, b] of richer) g[b].push(a);
  const ans = new Array(n).fill(-1);
  const dfs = (u) => {
    if (ans[u] !== -1) return ans[u];
    ans[u] = u;
    for (const v of g[u]) {
      const cand = dfs(v);
      if (quiet[cand] < quiet[ans[u]]) ans[u] = cand;
    }
    return ans[u];
  };
  for (let i = 0; i < n; i++) dfs(i);
  return ans;
}

import java.util.*;
class Solution {
  List<List<Integer>> g; int[] ans, quiet;
  public int[] loudAndRich(int[][] richer, int[] quiet) {
    int n = quiet.length;
    this.quiet = quiet;
    g = new ArrayList<>();
    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
    for (int[] r : richer) g.get(r[1]).add(r[0]);
    ans = new int[n]; Arrays.fill(ans, -1);
    for (int i = 0; i < n; i++) dfs(i);
    return ans;
  }
  int dfs(int u) {
    if (ans[u] != -1) return ans[u];
    ans[u] = u;
    for (int v : g.get(u)) {
      int cand = dfs(v);
      if (quiet[cand] < quiet[ans[u]]) ans[u] = cand;
    }
    return ans[u];
  }
}

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<vector<int>> g; vector<int> ans, quiet;
    int dfs(int u) {
        if (ans[u] != -1) return ans[u];
        ans[u] = u;
        for (int v : g[u]) {
            int cand = dfs(v);
            if (quiet[cand] < quiet[ans[u]]) ans[u] = cand;
        }
        return ans[u];
    }
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& q) {
        int n = q.size();
        quiet = q; g.assign(n, {}); ans.assign(n, -1);
        for (auto &r : richer) g[r[1]].push_back(r[0]);
        for (int i = 0; i < n; i++) dfs(i);
        return ans;
    }
};

Explanation

For each person we want the quietest person among everyone who is at least as rich. Instead of checking everyone every time, we build a graph and let answers bubble up from richer people.

We build an edge from b to a whenever a is richer than b (line g[b].append(a)). So following edges from a person leads you to all the people richer than them.

Then we run a DFS with memoization. dfs(u) returns the quietest person reachable from u (including u). It starts by assuming u itself is quietest, then asks each richer neighbor v for their quietest answer and keeps whoever has the smaller quiet value. Once computed, ans[u] is cached so we never redo work.

Because answers are stored, each person and edge is processed once, giving O(V + E).

Example: for person 0, following richer edges reaches people including person 5, whose quietness 1 is the lowest, so answer[0] = 5.

Time: O(V + E) Space: O(V + E)