LeetCode 851: Loud and Rich
Problem Description
Explanation
To solve this problem, we can build a graph where each node represents a person and each directed edge represents the relationship that a person has more money than another person. Then, we can perform a depth-first search (DFS) starting from each person to find the person with the minimum quietness among those who have equal to or more money.
- Construct a directed graph based on the richer array.
- Initialize an array
answerwith -1 for all people. - Perform a DFS for each person to find the quietest person with equal to or more money.
Time Complexity: O(n^2)
Space Complexity: O(n)
Solutions
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[] pair : richer) {
graph.get(pair[1]).add(pair[0]);
}
int[] answer = new int[n];
Arrays.fill(answer, -1);
for (int i = 0; i < n; i++) {
if (answer[i] == -1) {
dfs(graph, quiet, answer, i);
}
}
return answer;
}
private int dfs(List<List<Integer>> graph, int[] quiet, int[] answer, int person) {
if (answer[person] != -1) {
return answer[person];
}
answer[person] = person;
for (int richerPerson : graph.get(person)) {
int candidate = dfs(graph, quiet, answer, richerPerson);
if (quiet[candidate] < quiet[answer[person]]) {
answer[person] = candidate;
}
}
return answer[person];
}
}Related LeetCode Problems
Loading editor...