# Loud and Rich
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/loud-and-rich)
Canonical: https://scaleengineer.com/dsa/problems/loud-and-rich
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Array, Graph
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal)
---
## Problem
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.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.

# Approaches
## Brute Force with Graph Traversal
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.
**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.
**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.
### Explanation
### 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.

```java
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;
    }
}
```
### Algorithm
*   **Graph Construction:** Build a directed graph where an edge from `u` to `v` signifies that `v` is richer than `u`. For each pair `[a, b]` in `richer`, add a directed edge from `b` to `a`.
*   **Iteration:** Loop through each person `i` from `0` to `n-1`.
*   **Traversal:** For each person `i`, perform a graph traversal (like BFS) starting from node `i` to find all reachable nodes (people richer than or equal to `i`).
*   **Find Minimum:** During the traversal for `i`, keep track of the person with the minimum `quiet` value encountered so far.
*   **Store Result:** After the traversal for `i` is complete, store the found person's index in `answer[i]`.
*   **Return:** After iterating through all people, return the `answer` array.

## Depth-First Search with Memoization
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.
**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.
**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).
### Explanation
### 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 if `answer[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 `person` to be `person` itself. Then, we iterate through all people `neighbor` who are richer than `person` (i.e., there's an edge `person -> neighbor`). For each `neighbor`, we recursively call `dfs(neighbor)`. This call returns the quietest person in the `neighbor`'s group. We then compare this candidate's quietness with our current best for `person` and update if necessary.
*   **Store and Return:** After checking all neighbors, we have found the final answer for `person`. We store it in `answer[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.

```java
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];
    }
}
```
### Algorithm
*   **Graph Construction:** Build a directed graph where an edge `u -> v` means `v` is richer than `u`. For `[a, b]` in `richer`, add edge `b -> a`.
*   **Memoization Setup:** Initialize an `answer` array of size `n` with 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] = person` as the initial best candidate.
    *   For each `neighbor` of `person` (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 `person` and update if a quieter person is found.
    *   Store and return the final result for `person` in `answer[person]`.
*   **Main Loop:** Iterate from `i = 0` to `n-1` and call `dfs(i)` to ensure the answer for every person is computed.
*   **Return:** Return the populated `answer` array.

# Solutions
### Java

```java
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];
      }
    }
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```