Problem Description

The "Loud and Rich" problem requires you to determine, for each person in a group, the quietest individual among all those who are at least as rich as that person (including themselves).

You are given:

• An integer n, the number of people labeled from 0 to n - 1.
• An array richer, where each element is a pair [a, b] meaning person a is richer than person b.
• An array quiet, where quiet[i] is the quietness score of person i (lower means quieter).

Constraints:

• There is at least one valid solution for each person.
• Do not reuse elements in an unintended way; each person's answer is independent.

Thought Process

At first glance, the problem seems to ask for a "minimum" quietness value among all people who are as rich or richer than each person. Since the "richer" relationships form a directed graph (with an edge from richer to poorer), it is tempting to consider, for each person, all people who can reach them via these relationships.

A brute-force approach would be, for each person, to traverse the graph and collect all people richer than or equal to them, then select the quietest. However, this would be inefficient, especially if the graph is large or dense.

To optimize, we can think in terms of memoization or dynamic programming: once we've computed the quietest person for one node, we can reuse this result for others. This leads us to a depth-first search (DFS) approach with memoization, treating the problem as a propagation of "quietest so far" information from richer to poorer.

Solution Approach

We'll model the "richer" information as a graph, where an edge from a to b means a is richer than b. For each person, we want to find the quietest person among themselves and all richer people.

1. Construct the Graph:
   • For each pair [a, b] in richer, add a to the list of "richer neighbors" for b.
2. DFS with Memoization:
   • For each person x, perform a DFS to find all richer people, keeping track of the quietest person found.
   • Use a memoization array so that once we have the answer for a person, we don't recompute it.
3. Initialization:
   • Initialize the answer for each person to themselves (since a person is always at least as rich as themselves).
4. Result:
   • After DFS, the answer array contains for each person the index of the quietest person among all who are at least as rich as them.

We use a hash map (or adjacency list) for the graph to allow O(1) lookups, and memoization to avoid redundant DFS traversals.

Example Walkthrough

Suppose richer = [[1,0],[2,1],[3,1]] and quiet = [3,2,5,4].

• The relationships are:
  • 1 is richer than 0
  • 2 is richer than 1
  • 3 is richer than 1
• Build the graph:
  • 0: [1]
  • 1: [2, 3]
  • 2: []
  • 3: []
• For person 0:
  • Richer people: 1, 2, 3
  • Quietness: 0(3), 1(2), 2(5), 3(4)
  • Quietest: 1 (quietness 2)
• For person 1:
  • Richer people: 2, 3
  • Quietness: 1(2), 2(5), 3(4)
  • Quietest: 1 (quietness 2)
• For person 2:
  • No one richer
  • Quietest: 2 (quietness 5)
• For person 3:
  • No one richer
  • Quietest: 3 (quietness 4)

The final answer is [1,1,2,3].

Time and Space Complexity

• Brute-force:
  • For each person, traverse all possible richer paths: O(n^2) or worse in dense graphs.
  • Space: O(n^2) if storing all paths.
• Optimized (DFS + Memoization):
  • Each node is visited once, and each edge is traversed once: O(n + E), where E is the number of richer relationships.
  • Space: O(n + E) for the graph and memoization array.

The optimized approach is efficient for large graphs, as each person's result is computed only once.

Summary

The "Loud and Rich" problem is a classic example of propagating minimum values through a directed acyclic graph. By modeling richer relationships as a graph and using DFS with memoization, we efficiently determine, for each person, the quietest among all those at least as rich as them. The key insight is to avoid recomputation by caching results, making the solution both elegant and efficient.

Code Implementation

class Solution:
    def loudAndRich(self, richer, quiet):
        from collections import defaultdict
        n = len(quiet)
        graph = defaultdict(list)
        for a, b in richer:
            graph[b].append(a)
        answer = [-1] * n

        def dfs(x):
            if answer[x] != -1:
                return answer[x]
            min_person = x
            for neighbor in graph[x]:
                candidate = dfs(neighbor)
                if quiet[candidate] < quiet[min_person]:
                    min_person = candidate
            answer[x] = min_person
            return min_person

        for i in range(n):
            dfs(i)
        return answer
      

class Solution {
public:
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
        int n = quiet.size();
        vector<vector<int>> graph(n);
        for (auto& r : richer) {
            graph[r[1]].push_back(r[0]);
        }
        vector<int> answer(n, -1);

        function<int(int)> dfs = [&](int x) {
            if (answer[x] != -1) return answer[x];
            int min_person = x;
            for (int neighbor : graph[x]) {
                int candidate = dfs(neighbor);
                if (quiet[candidate] < quiet[min_person])
                    min_person = candidate;
            }
            answer[x] = min_person;
            return min_person;
        };

        for (int i = 0; i < n; ++i)
            dfs(i);
        return answer;
    }
};
      

class Solution {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; ++i) graph.add(new ArrayList<>());
        for (int[] r : richer) {
            graph.get(r[1]).add(r[0]);
        }
        int[] answer = new int[n];
        Arrays.fill(answer, -1);

        returnInt[] dfs = new int[1];
        for (int i = 0; i < n; ++i) {
            dfs(i, graph, quiet, answer);
        }
        return answer;
    }

    private int dfs(int x, List<List<Integer>> graph, int[] quiet, int[] answer) {
        if (answer[x] != -1) return answer[x];
        int minPerson = x;
        for (int neighbor : graph.get(x)) {
            int candidate = dfs(neighbor, graph, quiet, answer);
            if (quiet[candidate] < quiet[minPerson]) minPerson = candidate;
        }
        answer[x] = minPerson;
        return minPerson;
    }
}
      

var loudAndRich = function(richer, quiet) {
    const n = quiet.length;
    const graph = Array.from({length: n}, () => []);
    for (const [a, b] of richer) {
        graph[b].push(a);
    }
    const answer = new Array(n).fill(-1);

    function dfs(x) {
        if (answer[x] !== -1) return answer[x];
        let minPerson = x;
        for (const neighbor of graph[x]) {
            const candidate = dfs(neighbor);
            if (quiet[candidate] < quiet[minPerson]) minPerson = candidate;
        }
        answer[x] = minPerson;
        return minPerson;
    }

    for (let i = 0; i < n; ++i) {
        dfs(i);
    }
    return answer;
};