Loud and Rich

Medium

Asked by:

38 views

Topics:

GraphsDynamic Programming

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] = [a_i, b_i] indicates that a_i has more money than b_i and an integer array quiet where quiet[i] is the quietness of the i^th 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 <= a_i, b_i < n
a_i!= b_i
All the pairs of richer are unique.
The observations in richer are all logically consistent.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum values for the `quiet` array and the size of the `richer` and `quiet` arrays? Are we concerned about integer overflow?
Is it possible for the `richer` graph to contain cycles? If so, how should I handle them?
If multiple people are equally rich and at least as quiet as person x, which one should I return as `answer[x]`?
Is it guaranteed that a solution always exists for each person x? If not, what should I return for `answer[x]` if no such richer person exists (e.g., -1)?
Is it possible for `richer` to be empty, indicating that nobody is richer than anyone else? What should the output be in this case?

Brute Force Solution

Approach

Imagine you have a group of people, and you want to find out who the richest quietest person is for each individual. The brute force method involves checking every single person to see who is richer and quieter than each person in the group.

Here's how the algorithm would work step-by-step:

For each person, we will create a list of all the people who are richer than them.
Then, from that list of richer people, we will select the quietest person from that richer subset.
If there is nobody richer, then the quietest person is simply themselves.
Repeat these steps for every person in the group to find the quietest richer person for each of them.

Code Implementation

def loud_and_rich_brute_force(richer, quiet):
    number_of_people = len(quiet)
    answer = [0] * number_of_people

    for person in range(number_of_people):
        # Initialize the richest quietest person to themselves
        richest_quietest_person = person

        for other_person in range(number_of_people):
            is_richer = False

            # Check if other_person is richer than person
            if other_person != person:
                queue = [other_person]
                visited = {other_person}

                while queue:
                    current_person = queue.pop(0)
                    if current_person == person:
                        is_richer = True
                        break

                    for richer_person_index in range(len(richer)):
                        if richer[richer_person_index][1] == current_person:
                            next_person = richer[richer_person_index][0]
                            if next_person not in visited:
                                queue.append(next_person)
                                visited.add(next_person)

            # Update richest_quietest_person if applicable
            if is_richer:
                if quiet[other_person] < quiet[richest_quietest_person]:
                    richest_quietest_person = other_person

        answer[person] = richest_quietest_person

    return answer

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n people. For each person, it potentially iterates through all other n-1 people to identify those who are richer. Finding the quietest among the richer subset could take up to n operations in the worst case for each person. Therefore, the total operations can be approximated as n * n, which simplifies to O(n²).

Space Complexity

O(N) – For each person, we create a list of richer people. In the worst-case scenario, where everyone is richer than the last person, each list could contain up to N-1 elements, where N is the number of people. Since we do this for each of the N people, we are essentially storing a total of N lists, with each list potentially having almost N elements, but since we are never instantiating all the lists at once, the space used is driven by the 'richest' lists, which could in aggregate be N. Therefore, the auxiliary space used is O(N).

Optimal Solution

Approach

The problem asks us to find, for each person, the quietest person who is at least as rich. We can use a clever trick called Dynamic Programming with Depth First Search. We'll build up our answers starting from the richest people and working our way down, ensuring we've considered all richer options before deciding on the quietest among them.

Here's how the algorithm would work step-by-step:

First, we need to understand who is richer than whom. Create a 'richer than' list for each person based on the given relationships.
Next, start with each person and use the 'richer than' list to explore all people who are richer than them (directly or indirectly).
As you explore, keep track of the quietest person you've found so far who is at least as rich as the starting person.
If you already know the quietest rich person for someone, don't recalculate it! Just use the stored answer. This is the dynamic programming part: remembering past work.
If you haven't calculated it, and you find someone richer who is quieter, update your quietest rich person.
Keep exploring until you've exhausted all richer people. The quietest person you found is the answer for the starting person.
Repeat this process for every person. The end result is a list where each entry tells you the quietest person at least as rich as the person at that position.

Code Implementation

def loud_and_rich(richer, quiet):
    number_of_people = len(quiet)
    richer_than = [[] for _ in range(number_of_people)]

    for richer_person, poorer_person in richer:
        richer_than[poorer_person].append(richer_person)

    answer = [None] * number_of_people

    def dfs(person):
        if answer[person] is not None:
            return answer[person]

        # Initialize the quietest person as the person themselves.
        quietest_rich_person = person

        for richer_person in richer_than[person]:
            # Recursively find the quietest richer person.
            current_quietest = dfs(richer_person)

            # Compare the quietness to update quietest_rich_person.
            if quiet[current_quietest] < quiet[quietest_rich_person]:
                quietest_rich_person = current_quietest

        answer[person] = quietest_rich_person
        return quietest_rich_person

    # Ensure each person's answer is calculated.
    for i in range(number_of_people):
        dfs(i)

    return answer

Big(O) Analysis

Time Complexity

O(n + m) – The algorithm iterates through each person (n) to find the quietest richer person. For each person, it potentially explores all individuals richer than them. This exploration uses Depth First Search (DFS) guided by the 'richer than' relationships, which are represented as edges (m) in a graph. In the worst case, DFS visits all reachable nodes from each starting node. Because we memoize the results of each DFS, ensuring each node is visited at most once. Therefore, the time complexity is O(n + m), where n represents the number of people and m is the number of richer-than relationships.

Space Complexity

O(N) – The 'richer than' list for each person will, in the worst case, store a list of all other people. This creates an adjacency list-like structure which takes O(N) space for each of the N people. We also store the results of the dynamic programming in an array of size N. Therefore, the total auxiliary space is dominated by these two components, both contributing O(N) space. The recursion stack can, in the worst case, grow to a depth of N, so also adds O(N) to the overall space complexity. Combining these, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
richer is null or empty	If richer is null or empty, initialize answer[i] = i for all i because there are no relationships and everyone is the richest at least as quiet as themselves.
quiet is null or empty	If quiet is null or empty, return an empty array as the required information is missing.
quiet array has only one element	If quiet has one element, the answer[0] is 0 as that person is the richest at least as quiet as themselves.
richer contains cycles (e.g., A > B > C > A)	Use memoization (dynamic programming) during the depth-first search to avoid infinite loops and redundant computations when cycles are present.
A person is richer than everyone else, and also the quietest.	The answer for every person will be this single person, and the algorithm should efficiently identify this.
The graph is disconnected. Several sets of richer people.	The algorithm must handle disconnected graphs by processing each connected component separately.
Large input sizes (N up to 500) causing potential stack overflow with deep recursion.	Implement an iterative approach using topological sort instead of a recursive DFS to mitigate stack overflow issues.
All people have the same quietness value.	In this case, for each person x, the answer should be the richest person among those richer than x and x itself; the quietness values do not filter anyone out.

richer is null or empty

How to Handle:

If richer is null or empty, initialize answer[i] = i for all i because there are no relationships and everyone is the richest at least as quiet as themselves.

quiet is null or empty

How to Handle:

If quiet is null or empty, return an empty array as the required information is missing.

quiet array has only one element

How to Handle:

If quiet has one element, the answer[0] is 0 as that person is the richest at least as quiet as themselves.

richer contains cycles (e.g., A > B > C > A)

How to Handle:

Use memoization (dynamic programming) during the depth-first search to avoid infinite loops and redundant computations when cycles are present.

A person is richer than everyone else, and also the quietest.

How to Handle:

The answer for every person will be this single person, and the algorithm should efficiently identify this.

The graph is disconnected. Several sets of richer people.

How to Handle:

The algorithm must handle disconnected graphs by processing each connected component separately.

Large input sizes (N up to 500) causing potential stack overflow with deep recursion.

How to Handle:

Implement an iterative approach using topological sort instead of a recursive DFS to mitigate stack overflow issues.

All people have the same quietness value.

How to Handle:

In this case, for each person x, the answer should be the richest person among those richer than x and x itself; the quietness values do not filter anyone out.