Loud and Rich

Problem Statement

In this scenario, we are dealing with a group of n people, each uniquely identified by a label from 0 to n-1. Each individual in the group possesses a distinct amount of money and exhibits a unique level of quietness. The relationships concerning who has more money than whom are given in the richer array, where each element [ai, bi] signifies that person ai is wealthier than person bi. Additionally, the quiet array provides the quietness level for each person, with quiet[i] representing the quietness of person i.

The task is to compute an array answer such that each element answer[x] points to the person y. This person y should be the least quiet among all individuals who are as wealthy as or wealthier than the person x, based on the information provided in the richer array.

In essence, for every individual x, we are to determine the individual y who not only has wealth equal to or greater than x but is also the quietest among that group, according to the quiet array.

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]

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.

Approach and Intuition

To solve this problem, we need a strategy to efficiently determine the least quiet person with wealth higher than or equal to each individual. Here is a step-by-step approach for achieving this:

1. Graph Construction:

   • Construct a directed graph from the richer array. Each pair [ai, bi] in richer can be viewed as a directed edge from node bi to ai, indicating ai is richer than bi.

2. Quietness Evaluation:

   • For each individual, ascertain all the people who have equal to or more money than them. This can be done through a traversal of the constructed graph starting from each node.

3. Choose the Least Quiet:

   • Query the set of reachable persons for each individual x (including x itself), and select the person y with the minimal value in the quiet array.

Graph Traversal Method:

• Depth-First Search (DFS) or Breadth-First Search (BFS):

  • Use DFS or BFS to traverse from each node and track the quietest person reachable using the quiet values. Memoization or storing intermediate results helps in minimizing repetitive calculations, especially when multiple nodes refer to the same richer nodes.

• Memoization:

  • Employ memoization to store the results of least quiet persons for each starting person to avoid redundant processing in overlapping sub-graphs.

Efficient Selection:

• Every time you traverse the graph and visit nodes (people), compare their quietness and update the least quiet candidate based on the minimal quiet value encountered.

By leveraging graph traversal techniques and memoization, this approach efficiently computes the desired answer array while ensuring all constraints and unique properties of the dataset (like the uniqueness in quiet values) are respected. This methodology guarantees that we make use of the structural properties of the data (directed acyclic graph nature of relationships in richer and uniqueness in quiet) to optimize our solution.

Solutions

class Solution {
    ArrayList<Integer>[] adjacencyList;
    int[] result;
    int[] quietness;

    public int[] solveLoudAndRich(int[][] richer, int[] quiet) {
        int size = quiet.length;
        adjacencyList = new ArrayList[size];
        result = new int[size];
        this.quietness = quiet;

        for (int i = 0; i < size; ++i)
            adjacencyList[i] = new ArrayList<>();

        for (int[] rich: richer)
            adjacencyList[rich[1]].add(rich[0]);

        Arrays.fill(result, -1);

        for (int i = 0; i < size; ++i)
            depthFirstSearch(i);
        return result;
    }

    public int depthFirstSearch(int index) {
        if (result[index] == -1) {
            result[index] = index;
            for (int neighbor: adjacencyList[index]) {
                int candidate = depthFirstSearch(neighbor);
                if (quietness[candidate] < quietness[result[index]])
                    result[index] = candidate;
            }
        }
        return result[index];
    }
}