#851

Medium

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Loud and Rich

Determine the quietest person richer than each individual using graph indegree analysis and topological ordering techniques.

array depth first search graph topological sort

Problem Statement

Given a group of n people labeled from 0 to n - 1, each with a unique amount of money and quietness level, determine for each person the quietest person who has equal to or more money. The richer relationships are provided as pairs richer[i] = [ai, bi] meaning ai is richer than bi, and quiet[i] denotes the quietness of person i.

Return an array answer where answer[x] = y such that y is the quietest among all people who are definitely richer than or as wealthy as person x. All richer pairs are logically consistent and unique. Your solution should handle up to 500 people efficiently.

Examples

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]

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]

Example details omitted.

Constraints

n == quiet.length
1 <= n <= 500
0 <= quiet[i] < n
All the values of quiet are unique.
0 <= richer.length <= n * (n - 1) / 2
0 <= ai, bi < n
ai != bi
All the pairs of richer are unique.
The observations in richer are all logically consistent.

Solution Approach

Graph Construction and Indegree Setup

Build a directed graph where edges point from richer to poorer individuals, then compute indegree for each node. Nodes with indegree 0 represent people who are not known to be poorer than anyone else. This sets up for topological processing of wealth chains.

Topological Sort and Quietness Propagation

Perform a topological sort using a queue of nodes with indegree 0. For each person popped, update the quietest person for all neighbors if the current person's quietness is lower. Decrease indegree of neighbors and enqueue when indegree reaches 0, ensuring all richer-to-poorer paths are considered.

Final Answer Extraction

After completing the topological sort, each person's quietest richer or equally wealthy person is tracked. Extract the answer array directly from this mapping, guaranteeing correctness because all possible richer paths have been explored via DFS ordering inherent in the topological sort.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(N^2)
Space	\mathcal{O}(N^2)

Time complexity is \mathcal{O}(N^2) because each person may connect to multiple others in the graph and updates propagate along edges. Space complexity is \mathcal{O}(N^2) for storing the adjacency list and tracking quietest person per node during topological traversal.

What Interviewers Usually Probe

Checking if you model richer relationships as a graph correctly.
Looking for proper indegree computation and queue usage for topological sort.
Ensuring quietness propagation follows the graph edges accurately.

Common Pitfalls or Variants

Common pitfalls

Failing to account for multiple richer paths leading to the same person and not updating quietness properly.
Confusing indegree direction and processing poorer-to-richer instead of richer-to-poorer.
Assuming the quietest person is always directly richer, ignoring transitive richer relationships.

Follow-up variants

Solve using DFS with memoization instead of explicit topological sorting.
Handle cases where richer relationships may form multiple disconnected wealth chains.
Adapt for dynamic updates where new richer relationships are added incrementally.

FAQ

What is the core pattern used in Loud and Rich?

The problem relies on graph indegree computation combined with topological ordering to propagate quietness along richer-to-poorer edges.

Can DFS replace topological sort in this problem?

Yes, DFS with memoization can traverse richer paths to compute the quietest person while avoiding redundant calculations.

What is the maximum number of people supported efficiently?

The solution handles up to 500 people, consistent with constraints on array length and edge count.

How do we handle multiple richer paths to the same person?

Always update the quietest person by comparing existing quietness with propagated values along each incoming richer path.

Is the answer array guaranteed to contain unique indices?

Not necessarily; the same person may be the quietest for multiple individuals, depending on transitive richer relationships.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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 ans

Continue Practicing

#329 longest increasing path in a matrix #802 find eventual safe states #924 minimize malware spread