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] < nquiet are unique.0 <= richer.length <= n * (n - 1) / 20 <= ai, bi < nai != biricher are unique.richer are all logically consistent.This approach involves representing the problem as a directed graph, where each edge indicates that one person is richer than another. We perform a Depth-First Search (DFS) from each node to find the quietest person that can potentially reach the given node using memoization to optimize the search process.
We create a directed graph where each node is a person and there is an edge u -> v if u is richer than v. We then perform a DFS from each node to determine the quietest person reachable starting from that node. The memoization helps in storing previously computed answers to avoid redundant calculations.
JavaScript
Java
C++
C#
Time Complexity: O(n + e), where n is the number of people and e is the number of relationships. Each node and edge is processed once.
Space Complexity: O(n + e), to store the graph and the answer array.
This approach involves using topological sorting to process the nodes in an order where each node processes its neighbors only after it has been considered. This sorts the nodes such that for any richer pair a -> b, 'a' appears before 'b'. We then traverse the graph to determine the quietest person for each node.
We first construct a graph and calculate in-degrees for each node. Using a queue (BFS approach), nodes with zero in-degree are processed first, ensuring an order where a richer person is processed before the one richer than them. For each node, update the answer to maintain the quietest reachable person using the quiet array.
Time Complexity: O(n + e), as each node and edge is processed.
Space Complexity: O(n + e), due to storing the graph and in-degrees.
| Approach | Complexity |
|---|---|
| Graph Representation and DFS with Memoization | Time Complexity: O(n + e), where n is the number of people and e is the number of relationships. Each node and edge is processed once. |
| Topological Sort Based Approach | Time Complexity: O(n + e), as each node and edge is processed. |
The unfair way I got good at Leetcode • Dave Burji • 596,377 views views
Watch 9 more video solutions →Practice Loud and Rich with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor