Leetcode 851. Loud and Rich

Problem Explanation:

The problem requires us to find out the least quiet person that has equal to or more money than each person in a group of people. The information about who has more money and the level of quietness is given in the form of arrays.

We can visualize this problem as a directed graph where each person is a node and edge from person A to person B signifies that person B has more money than person A. Now for each person, we have to find a node in the directed path where quietness is the least.

This problem can be solved using Depth-First Search (DFS) on the directed graph.

Let's consider the given example to understand how the algorithm will work step by step.

Example:

Suppose we have richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]

People who have more money are visualized as a directed graph: 0<--1<--2 | ^ | | v | 3<--4 | ^ | | v | 7<--5 | v 6

For each node (person), we start a DFS to find the node with the minimum quietness.

Python Solution:

1
2python
3class Solution:
4    def loudAndRich(self, richer, quiet):
5        n = len(quiet)
6        graph = [[] for _ in range(n)]
7        answer = [None]*n
8
9        for u, v in richer:
10            graph[v].append(u)
11
12        def dfs(node):
13            # If this node is already visited, return the answer
14            if answer[node] is not None:
15                return answer[node]
16            # Initialize the answer[node] as node
17            answer[node] = node
18            for child in graph[node]:
19                temp_node = dfs(child)
20                # Update the answer if a less quiet person is found
21                if quiet[answer[node]] > quiet[temp_node]:
22                    answer[node] = temp_node
23            return answer[node]
24        
25        return [dfs(node) for node in range(n)]

Java Solution:

1
2java
3class Solution {
4    List<Integer>[] graph;
5    int[] quiet,res;
6    public int[] loudAndRich(int[][] richer, int[] quiet) {
7        int n = quiet.length;
8        graph = new ArrayList[n];
9        this.quiet = quiet;
10        res = new int[n];
11        for(int i = 0; i<n; i++)
12            graph[i] = new ArrayList<>();
13        for(int i = 0; i<n; i++)
14            res[i] = -1;
15        for(int[] pair: richer)
16            graph[pair[1]].add(pair[0]);
17        for(int i = 0; i<n; i++)
18            dfs(i);
19        return res;
20    }
21    public int dfs(int node){
22        if(res[node] >= 0)
23            return res[node];
24        res[node] = node;
25        for(int neighbor: graph[node]){
26            if(quiet[res[node]] > quiet[dfs(neighbor)])
27                res[node] = dfs(neighbor);
28        }
29        return res[node];
30    }
31}

JavaScript Solution:

1
2javascript
3class Solution {
4    constructor() {
5        this.graph = [];
6        this.quiet = []
7        this.answer = [];
8    }
9    loudAndRich(richer, quiet) {
10        const n = quiet.length;
11        this.graph = Array(n).fill().map(() => []);
12        this.answer = Array(n).fill(-1);
13        this.quiet = quiet;
14        
15        for (let [u, v] of richer) {
16            this.graph[u].push(v);
17        }
18        
19        for(let i = 0; i < n; i++) {
20            this.dfs(i);
21        }
22        
23        return this.answer;
24    }
25    dfs(node) {
26        if (this.answer[node] === -1) {
27            this.answer[node] = node;
28            for (let neighbor of this.graph[node]) {
29                const candidate = this.dfs(neighbor);
30                if (this.quiet[candidate] < this.quiet[this.answer[node]]) {
31                    this.answer[node] = candidate;
32                }
33            }
34        }
35        
36        return this.answer[node];
37    }
38};

C++ Solution:

1
2cpp
3class Solution {
4public:
5    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
6        int n = quiet.size();
7        vector<int> answer(n, -1);
8        vector<vector<int>> graph(n);
9
10        for (const auto& r : richer) {
11            graph[r[1]].push_back(r[0]);
12        }
13
14        for (int i = 0; i < n; ++i) {
15            dfs(graph, i, quiet, answer);
16        }
17
18        return answer;
19    }
20    
21    int dfs(vector<vector<int>>& graph, int node, vector<int>& quiet, vector<int>& answer) {
22        if (answer[node] != -1) {
23            return answer[node];
24        }
25        answer[node] = node;
26
27        for (const auto& neighbor : graph[node]) {
28            int candidate = dfs(graph, neighbor, quiet, answer);
29            if (quiet[candidate] < quiet[answer[node]]) {
30                answer[node] = candidate;
31            }
32        }
33        return answer[node];
34    }
35};

C# Solution:

1
2csharp
3public class Solution {
4    private List<int>[] graph;
5    private int[] quiet, answer;
6    public int[] LoudAndRich(int[][] richer, int[] quiet) {
7        int n = quiet.Length;
8        graph = new List<int>[n];
9        this.quiet = quiet;
10        answer = new int[n];
11        for(int i = 0; i<n; i++) {
12            graph[i] = new List<int>();
13            answer[i] = -1;
14        }
15        foreach(var pair in richer)
16            graph[pair[1]].Add(pair[0]);
17        for(int i = 0; i<n; i++)
18            dfs(i);
19        return answer;
20    }
21    public int dfs(int node){
22        if(answer[node] >= 0)
23            return answer[node];
24        answer[node] = node;
25        foreach(int neighbor in graph[node]) {
26            if(quiet[answer[node]] > quiet[dfs(neighbor)])
27                answer[node] = dfs(neighbor);
28        }
29        return answer[node];
30    }
31}

In all solutions, we are following the same approach of creating a directed graph from the richer array and then running DFS on each node to find the least quiet person among all people who definitely have equal to or more money than the person.## Solution Explanation:

The first step in solving this problem is to understand the graph. In the graph, each person in the richer array is a node. Edges in the graph are taken from the richer array, where an edge from person A to person B signifies that person B has more money than person A.

The algorithm starts with a DFS (Depth-First Search) from each node (person). The DFS is carried out in such a way that it keeps track of the least quiet person in the path. For this, we maintain an answer array. For each node, if it is visited for the first time, we store the node itself in the answer array. Then, we explore each child (neighbors in the graph) of the node and update the answer for the node with the child, whose quietness is less than the previously stored answer.

In short, nearly all solutions utilize the depth-first search algorithm. Starting from each person (or node in the graph), we perform a DFS to find the person in the directed path who is least quiet. We store results in an answer list or array for each person before we move on to the next one, which saves computational power as we don't need to recompute the answer for any person.

Hence, all solutions have a time complexity of O(N), where N is the total number of people as we are performing DFS from each person once.

The space complexity is also O(N), to store the graph, answer, and quiet arrays or lists. For Python and JavaScript solutions, as recursion is used, the maximum depth of recursion can also add to the space complexity, and it can go up to N in the worst case.

Conclusion

In summary, we utilized depth-first search here to solve a problem that can be visualized and modelled as a directed graph. This algorithm and its application in this problem further demonstrate the flexibility and utility of DFS, as we are able to use it to find the least "quiet" person that each person in a group can reach under given conditions. This problem-solving approach and these solutions can be applied in many situations, for example, in social network analysis, citation networks, PageRank, etc., where such modelling as directed graphs and such search algorithms as DFS are commonly used.