https://leetcode.com/problems/loud-and-rich/description/
X. DFS
https://leetcode.com/problems/loud-and-rich/discuss/137918/C%2B%2BJavaPython-Concise-DFS
https://leetcode.com/problems/loud-and-rich/discuss/137987/Java-BFS
In a group of N people (labelled
0, 1, 2, ..., N-1
), each person has different amounts of money, and different levels of quietness.
For convenience, we'll call the person with label
x
, simply "person x
".
We'll say that
richer[i] = [x, y]
if person x
definitely has more money than person y
. Note that richer
may only be a subset of valid observations.
Also, we'll say
quiet[x] = q
if person x has quietness q
.
Now, return
answer
, where answer[x] = y
if y
is the least quiet person (that is, the person y
with the smallest value of quiet[y]
), among all people who definitely have equal to or more money than person x
.
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: answer[0] = 5. Person 5 has more money than 3, which has more money than 1, which has more money than 0. The only person who is quieter (has lower quiet[x]) is person 7, but it isn't clear if they have more money than person 0. answer[7] = 7. Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7. The other answers can be filled out with similar reasoning.
Note:
1 <= quiet.length = N <= 500
0 <= quiet[i] < N
, allquiet[i]
are different.0 <= richer.length <= N * (N-1) / 2
0 <= richer[i][j] < N
richer[i][0] != richer[i][1]
richer[i]
's are all different.- The observations in
richer
are all logically consistent.
https://leetcode.com/problems/loud-and-rich/discuss/137918/C%2B%2BJavaPython-Concise-DFS
The description is not easy to understand.
In fact it's a basic dfs traversal problem.
For every people, call a sub function
Also we will note this answer to avoid repeated calculation.
In fact it's a basic dfs traversal problem.
For every people, call a sub function
dfs
to compare the quiet
with others, who is richer than him.Also we will note this answer to avoid repeated calculation.
Time Complexity:
O(richer.length),
Sub function
O(richer.length),
Sub function
dfs
traverse every people only once, and every richer
is traversed only one once. HashMap<Integer, List<Integer>> richer2 = new HashMap<>();
int res[];
public int[] loudAndRich(int[][] richer, int[] quiet) {
int n = quiet.length;
for (int i = 0; i < n; ++i) richer2.put(i, new ArrayList<Integer>());
for (int[] v : richer) richer2.get(v[1]).add(v[0]);
res = new int[n]; Arrays.fill(res, -1);
for (int i = 0; i < n; i++) dfs(i, quiet);
return res;
}
int dfs(int i, int[] quiet) {
if (res[i] >= 0) return res[i];
res[i] = i;
for (int j : richer2.get(i)) if (quiet[res[i]] > quiet[dfs(j, quiet)]) res[i] = res[j];
return res[i];
}
Consider the directed graph with edge
x -> y
if y
is richer than x
.
For each person
x
, we want the quietest person in the subtree at x
.
Algorithm
Construct the graph described above, and say
dfs(person)
is the quietest person in the subtree at person
. Notice because the statements are logically consistent, the graph must be a DAG - a directed graph with no cycles.
Now
dfs(person)
is either person
, or min(dfs(child) for child in person)
. That is to say, the quietest person in the subtree is either the person
itself, or the quietest person in some subtree of a child of person
.
We can cache values of
dfs(person)
as answer[person]
, when performing our post-order traversal of the graph. That way, we don't repeat work. This technique reduces a quadratic time algorithm down to linear time.- Time Complexity: , where is the number of people.
- Space Complexity: , the space used by the
answer
, and the implicit call stack ofdfs
.
ArrayList<Integer>[] graph;
int[] answer;
int[] quiet;
public int[] loudAndRich(int[][] richer, int[] quiet) {
int N = quiet.length;
graph = new ArrayList[N];
answer = new int[N];
this.quiet = quiet;
for (int node = 0; node < N; ++node)
graph[node] = new ArrayList<Integer>();
for (int[] edge : richer)
graph[edge[1]].add(edge[0]);
Arrays.fill(answer, -1);
for (int node = 0; node < N; ++node)
dfs(node);
return answer;
}
public int dfs(int node) {
if (answer[node] == -1) {
answer[node] = node;
for (int child : graph[node]) {
int cand = dfs(child);
if (quiet[cand] < quiet[answer[node]])
answer[node] = cand;
}
}
return answer[node];
}
https://leetcode.com/problems/loud-and-rich/discuss/137987/Java-BFS
public int[] loudAndRich(int[][] richer, int[] quiet) {
int n = quiet.length;
// construct "adjacent list" , record richer people
List<List<Integer>> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
list.add(new ArrayList<>());
}
for (int i = 0; i < richer.length; i++) {
list.get(richer[i][1]).add(richer[i][0]);
}
int[] result = new int[n];
for (int i = 0; i < n; i++) {
// no one is richer than i
if (list.get(i).size() == 0) {
result[i] = i;
continue;
}
// otherwise,do BFS
result[i] = bfs(list, quiet, i);
}
return result;
}
private int bfs(List<List<Integer>> list, int[] quiet, int index) {
int result = index;
int q = Integer.MAX_VALUE; // least quiet
boolean[] visited = new boolean[quiet.length];
Queue<Integer> queue = new LinkedList<>();
visited[index] = true;
queue.offer(index);
while (!queue.isEmpty()) {
int curr = queue.poll();
if (quiet[curr] < q) {
q = quiet[curr];
result = curr;
}
if (list.get(curr).size() != 0) {
for (int next : list.get(curr)) {
if (visited[next]) {
continue;
}
queue.offer(next);
visited[next] = true;
}
}
}
return result;
}