Loud and Rich
MedPrompt
There is a group of n people labeled from 0 to n - 1 where each person has a different amount of money and a different level of quietness.
You are given an array richer where richer[i] = [ai, bi] indicates that ai has more money than bi and an integer array quiet where quiet[i] is the quietness of the ith person. All the given data in richer are logically correct (i.e., the data will not lead you to a situation where x is richer than y and y is richer than x at the same time).
Return an integer array 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 the 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 is not 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.Example 2:
Input: richer = [], quiet = [0]
Output: [0]
Constraints:
n == quiet.length1 <= n <= 5000 <= quiet[i] < n- All the values of
quietare unique. 0 <= richer.length <= n * (n - 1) / 20 <= ai, bi < nai != bi- All the pairs of
richerare unique. - The observations in
richerare all logically consistent.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves modeling the relationships as a directed graph. For each person, we perform a separate graph traversal (like Breadth-First Search or Depth-First Search) to find all people who are richer than or equal to them. During the traversal, we keep track of the quietest person found.
Algorithm
- Graph Construction: Build a directed graph where an edge from
utovsignifies thatvis richer thanu. For each pair[a, b]inricher, add a directed edge frombtoa. - Iteration: Loop through each person
ifrom0ton-1. - Traversal: For each person
i, perform a graph traversal (like BFS) starting from nodeito find all reachable nodes (people richer than or equal toi). - Find Minimum: During the traversal for
i, keep track of the person with the minimumquietvalue encountered so far. - Store Result: After the traversal for
iis complete, store the found person's index inanswer[i]. - Return: After iterating through all people, return the
answerarray.
Walkthrough
1. Graph Construction
We first build a directed graph from the richer array. An edge from person u to person v (u -> v) will signify that v is richer than u. So, for each pair [a, b] in richer (meaning a is richer than b), we add a directed edge from b to a. An adjacency list is a suitable way to represent this graph.
2. Iterate and Traverse
We initialize an answer array of size n. Then, we iterate through each person i from 0 to n-1.
3. Find Quietest Person
For each person i, we start a graph traversal (e.g., BFS) from node i. The goal of this traversal is to visit all nodes reachable from i, which corresponds to the set of people richer than or equal to i.
We use a queue for BFS and a visited set to keep track of visited nodes in the current traversal. We initialize the search with person i, who is also the initial candidate for the quietest person.
As we traverse the graph, whenever we encounter a new person j, we compare their quietness quiet[j] with the minimum quietness found so far. If quiet[j] is smaller, we update our candidate for the quietest person.
After the traversal for person i is complete, the candidate we found is the answer for answer[i].
We repeat this process for all n people.
class Solution { public int[] loudAndRich(int[][] richer, int[] quiet) { int n = quiet.length; List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int[] r : richer) { adj.get(r[1]).add(r[0]); // Edge from less rich to more rich } int[] answer = new int[n]; for (int i = 0; i < n; i++) { int quietestPerson = i; Queue<Integer> queue = new LinkedList<>(); queue.add(i); Set<Integer> visited = new HashSet<>(); visited.add(i); while (!queue.isEmpty()) { int u = queue.poll(); if (quiet[u] < quiet[quietestPerson]) { quietestPerson = u; } for (int v : adj.get(u)) { if (!visited.contains(v)) { visited.add(v); queue.add(v); } } } answer[i] = quietestPerson; } return answer; }}Complexity
Time
O(N * (N + R)), where N is the number of people and R is the number of richness comparisons. For each of the N people, we perform a graph traversal which can take up to O(N + R) time in the worst case (a connected graph).
Space
O(N + R), where N is the number of people and R is the number of relations. O(N+R) is for the adjacency list. For each traversal, the queue and visited set can take up to O(N) space.
Trade-offs
Pros
Simple to understand and implement.
Cons
Highly inefficient due to redundant computations. The traversal for one person might largely overlap with the traversal for another, but this work is not reused.
May result in a 'Time Limit Exceeded' error on larger test cases.
This approach improves upon the brute-force method by avoiding redundant computations. We can think of this problem as finding a property for each node in a Directed Acyclic Graph (DAG), where the property of a node depends on the properties of its successors. This structure is perfect for a dynamic programming approach, which can be implemented using Depth-First Search (DFS) with memoization.
Algorithm
- Graph Construction: Build a directed graph where an edge
u -> vmeansvis richer thanu. For[a, b]inricher, add edgeb -> a. - Memoization Setup: Initialize an
answerarray of sizenwith a sentinel value (e.g., -1) to act as a memoization table. - DFS Function: Create a recursive function
dfs(person):- If
answer[person]is not -1, return the stored value. - Initialize
answer[person] = personas the initial best candidate. - For each
neighborofperson(richer people):- Recursively call
dfs(neighbor)to get the quietest person in that subproblem. - Compare the quietness of the returned candidate with the current best for
personand update if a quieter person is found.
- Recursively call
- Store and return the final result for
personinanswer[person].
- If
- Main Loop: Iterate from
i = 0ton-1and calldfs(i)to ensure the answer for every person is computed. - Return: Return the populated
answerarray.
Walkthrough
1. Graph Construction
Same as the previous approach, we build a directed graph where an edge u -> v means v is richer than u. For each [a, b] in richer, we add an edge from b to a.
2. Memoization
We use an answer array to store the results. We initialize it with a sentinel value (e.g., -1) to indicate that the answer for a person has not yet been computed. This array acts as our memoization table.
3. Recursive DFS
We define a recursive function, dfs(person), that finds and returns the index of the quietest person in the group of person (i.e., person and all people richer than person).
- Base Case/Memoization Check: Inside
dfs(person), we first check ifanswer[person]has already been computed (i.e., not -1). If so, we return the stored value immediately. - Recursive Step: If not computed, we initialize the quietest person for the current
personto bepersonitself. Then, we iterate through all peopleneighborwho are richer thanperson(i.e., there's an edgeperson -> neighbor). For eachneighbor, we recursively calldfs(neighbor). This call returns the quietest person in theneighbor's group. We then compare this candidate's quietness with our current best forpersonand update if necessary. - Store and Return: After checking all neighbors, we have found the final answer for
person. We store it inanswer[person]and return it.
4. Main Loop
We iterate through all people from 0 to n-1 and call dfs(i) for each person i. The memoization ensures that the dfs logic for any given person is executed only once.
class Solution { List<List<Integer>> adj; int[] quiet; int[] answer; public int[] loudAndRich(int[][] richer, int[] quiet) { int n = quiet.length; this.quiet = quiet; this.adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int[] r : richer) { adj.get(r[1]).add(r[0]); // Edge from less rich to more rich } this.answer = new int[n]; Arrays.fill(answer, -1); for (int i = 0; i < n; i++) { dfs(i); } return answer; } private int dfs(int person) { if (answer[person] != -1) { return answer[person]; } // Initially, the person themselves is the quietest in their group answer[person] = person; // Explore richer people for (int richerPerson : adj.get(person)) { int candidate = dfs(richerPerson); if (quiet[candidate] < quiet[answer[person]]) { answer[person] = candidate; } } return answer[person]; }}Complexity
Time
O(N + R). Each node `person` is visited by the `dfs` function once due to memoization. During that visit, we iterate through its outgoing edges. Therefore, each node and each edge is processed a constant number of times. N is the number of people, R is the number of relations.
Space
O(N + R). O(N+R) for the adjacency list. The recursion depth can go up to O(N) in the worst case (a long chain), contributing to the space complexity. The `answer` array takes O(N) space.
Trade-offs
Pros
Very efficient, with a time complexity linear in the size of the graph.
It's an optimal solution as we must look at every person and every relation at least once.
Cons
Slightly more complex to implement due to recursion.
The recursion depth could be large for a long chain of rich-poor relationships, potentially leading to a stack overflow error in some environments (though unlikely with N <= 500).
Solutions
Solution
class Solution {private List<Integer>[] g;private int n;private int[] quiet;private int[] ans;public int[] loudAndRich(int[][] richer, int[] quiet) { n = quiet.length; this.quiet = quiet; g = new List[n]; ans = new int[n]; Arrays.fill(ans, -1); Arrays.setAll(g, k->new ArrayList<>()); for (var r : richer) { g[r[1]].add(r[0]); } for (int i = 0; i < n; ++i) { dfs(i); } return ans; }private void dfs(int i) { if (ans[i] != -1) { return; } ans[i] = i; for (int j : g[i]) { dfs(j); if (quiet[ans[j]] < quiet[ans[i]]) { ans[i] = ans[j]; } } }}class Solution {public: vector<int> loudAndRich(vector<vector<int>> &richer, vector<int> &quiet) { int n = quiet.size(); vector<vector<int>> g(n); for (auto &r : richer) { g[r[1]].push_back(r[0]); } vector<int> ans(n, -1); function<void(int)> dfs = [&](int i) { if (ans[i] != -1) { return; } ans[i] = i; for (int j : g[i]) { dfs(j); if (quiet[ans[j]] < quiet[ans[i]]) { ans[i] = ans[j]; } } }; for (int i = 0; i < n; ++i) { dfs(i); } return ans; }};class Solution: def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]: def dfs(i: int): if ans[i] != - 1: return ans[i] = i for j in g[i]: dfs(j) if quiet[ans[j]] < quiet[ans[i]]: ans[i] = ans[j] g = defaultdict(list) for a, b in richer: g[b]. append(a) n = len(quiet) ans = [- 1] * n for i in range(n): dfs(i) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.