# LeetCode 851: Loud and Rich

## Problem Restatement

We are given `n` people labeled from `0` to `n - 1`.

Each person has:

| Data | Meaning |
|---|---|
| `quiet[i]` | Quietness level of person `i` |
| `richer[j] = [a, b]` | Person `a` is richer than person `b` |

For every person `x`, we need to find the quietest person among all people who are at least as rich as `x`.

This includes:

1. Person `x`
2. Everyone directly richer than `x`
3. Everyone indirectly richer than `x`

Return an array `answer`, where:

```python
answer[x]
```

is the index of the quietest person among all people who have at least as much money as person `x`.

The richer information is logically valid, so it does not contain contradictions or cycles. The richer relations form a directed acyclic graph.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `richer`, a list of richer relationships |
| Input | `quiet`, where `quiet[i]` is the quietness of person `i` |
| Output | `answer`, where `answer[i]` is the quietest person among people richer than or equal to `i` |

Function shape:

```python
class Solution:
    def loudAndRich(self, richer: list[list[int]], quiet: list[int]) -> list[int]:
        ...
```

## Examples

Consider:

```python
richer = [[1, 0], [2, 1], [3, 1]]
quiet = [3, 2, 5, 4]
```

The relationships mean:

| Relationship | Meaning |
|---|---|
| `[1, 0]` | Person `1` is richer than person `0` |
| `[2, 1]` | Person `2` is richer than person `1` |
| `[3, 1]` | Person `3` is richer than person `1` |

For person `0`, the people who are at least as rich are:

```python
0, 1, 2, 3
```

Their quiet values are:

| Person | Quiet |
|---|---|
| `0` | `3` |
| `1` | `2` |
| `2` | `5` |
| `3` | `4` |

The quietest person is person `1`, so:

```python
answer[0] = 1
```

For person `2`, nobody in the given information is richer than person `2`.

So the only candidate is person `2`, and:

```python
answer[2] = 2
```

## First Thought: Brute Force

A direct approach is:

For each person `x`:

1. Search for every person who is richer than `x`
2. Also search for people richer than those people
3. Compare quiet values
4. Return the quietest person found

This is graph reachability.

If we perform a fresh DFS or BFS for every person, the same richer chains may be visited many times.

For example, if many people are poorer than person `5`, then the richer chain above person `5` may be recomputed repeatedly.

## Problem With Brute Force

Let:

```python
n = len(quiet)
m = len(richer)
```

A fresh graph traversal for every person can cost up to:

```python
O(n * (n + m))
```

That is too much when the graph has many relationships.

We need to reuse answers.

## Key Insight

The answer for a person depends on the answers of people richer than them.

If person `a` is richer than person `b`, then when computing the answer for `b`, we should consider:

1. Person `b`
2. Person `a`
3. Everyone at least as rich as person `a`

So if we already know the answer for `a`, we can use it directly.

That suggests DFS with memoization.

Build a graph where each edge points from a poorer person to a richer person.

For a relationship:

```python
[a, b]
```

person `a` is richer than person `b`.

So we add:

```python
graph[b].append(a)
```

Now, starting from any person, DFS follows edges toward richer people.

## Algorithm

Create an adjacency list `graph`.

For each pair `[rich, poor]` in `richer`:

```python
graph[poor].append(rich)
```

Create an answer array:

```python
answer = [-1] * n
```

Here, `answer[x] == -1` means the answer for person `x` has not been computed yet.

Define `dfs(x)`:

1. If `answer[x]` is already known, return it.
2. Start with `x` as the best candidate.
3. For every richer person `y` in `graph[x]`:
   1. Compute `dfs(y)`
   2. Compare the quietness of the returned candidate with the current best candidate
   3. Keep the quieter one
4. Store the result in `answer[x]`.
5. Return `answer[x]`.

Finally, call `dfs(i)` for every person `i`.

## Correctness

For each person `x`, `dfs(x)` considers person `x` first.

Then it visits every directly richer person `y`.

For each such `y`, `dfs(y)` returns the quietest person among all people who are at least as rich as `y`.

Since `y` is richer than `x`, everyone at least as rich as `y` is also at least as rich as `x`.

Therefore, comparing `x` with every `dfs(y)` covers all valid candidates for person `x`.

The graph has no cycles, so the recursive search eventually stops.

Memoization does not change the result. It only reuses a value after it has already been fully computed.

Thus, for every person `x`, `answer[x]` is the quietest person among all people with at least as much money as `x`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + m)` | Each person and relationship is processed through memoized DFS |
| Space | `O(n + m)` | The graph stores `m` edges, and the answer array stores `n` values |

The recursion stack can also take up to `O(n)` space in the longest richer chain.

## Implementation

```python
from collections import defaultdict

class Solution:
    def loudAndRich(self, richer: list[list[int]], quiet: list[int]) -> list[int]:
        n = len(quiet)
        graph = defaultdict(list)

        for rich, poor in richer:
            graph[poor].append(rich)

        answer = [-1] * n

        def dfs(person: int) -> int:
            if answer[person] != -1:
                return answer[person]

            best = person

            for richer_person in graph[person]:
                candidate = dfs(richer_person)

                if quiet[candidate] < quiet[best]:
                    best = candidate

            answer[person] = best
            return best

        for person in range(n):
            dfs(person)

        return answer
```

## Code Explanation

We first build the graph:

```python
graph = defaultdict(list)

for rich, poor in richer:
    graph[poor].append(rich)
```

This means each person points to people known to be richer.

For example:

```python
richer = [[1, 0]]
```

creates:

```python
graph[0] = [1]
```

So from person `0`, we can move to person `1`.

The `answer` array is also our memo table:

```python
answer = [-1] * n
```

When `answer[person] == -1`, that person's result has not been computed.

Inside DFS:

```python
best = person
```

A person is always a valid candidate for themselves because the problem asks for people with equal or more money.

Then we inspect every richer person:

```python
for richer_person in graph[person]:
    candidate = dfs(richer_person)
```

The call `dfs(richer_person)` gives us the quietest person among all people at least as rich as `richer_person`.

If that candidate is quieter than the current best, we update:

```python
if quiet[candidate] < quiet[best]:
    best = candidate
```

At the end, we cache the result:

```python
answer[person] = best
```

This prevents repeated work when multiple poorer people share the same richer chain.

## Testing

```python
def test_loud_and_rich():
    s = Solution()

    richer = [
        [1, 0],
        [2, 1],
        [3, 1],
    ]
    quiet = [3, 2, 5, 4]
    assert s.loudAndRich(richer, quiet) == [1, 1, 2, 3]

    richer = []
    quiet = [0]
    assert s.loudAndRich(richer, quiet) == [0]

    richer = []
    quiet = [2, 0, 1]
    assert s.loudAndRich(richer, quiet) == [0, 1, 2]

    richer = [[0, 1], [1, 2], [2, 3]]
    quiet = [3, 2, 1, 0]
    assert s.loudAndRich(richer, quiet) == [0, 1, 2, 3]

    richer = [[0, 1], [0, 2], [1, 3], [2, 3]]
    quiet = [1, 3, 2, 4]
    assert s.loudAndRich(richer, quiet) == [0, 0, 0, 0]

    print("all tests passed")

test_loud_and_rich()
```

Test meaning:

| Test | Why |
|---|---|
| Small graph with branching richer paths | Checks transitive richer relationships |
| One person | Minimum input |
| No richer relationships | Every person answers themselves |
| Linear richer chain | Checks recursive propagation |
| Diamond-shaped graph | Checks shared richer paths and memoization |