We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Loud and Rich

Number: 881

Difficulty: Medium

Paid? No

Companies: PayPal, Microsoft, Uber, Amazon

Problem Description

Given a group of n people with unique amounts of money and distinct quietness values, determine for each person the quietest person among those who are at least as rich as them. The richer relationship is provided as pairs [a, b] meaning person a is richer than person b. The goal is to output an array where each index x contains the index of the person with the lowest quiet value among all people who are equal to or richer than x.

Key Insights

  • Model the problem as a graph where an edge from b to a indicates that a is richer than b.
  • Use DFS or topological sort to traverse the graph and propagate the quietness information.
  • Utilize memoization to avoid redundant DFS traversals and optimize performance.
  • At each node, compute the minimum quiet value by comparing the node itself with all of its richer neighbors.

Space and Time Complexity

Time Complexity: O(V + E) where V is the number of people and E is the number of richer relationships. Space Complexity: O(V + E) for the graph storage and recursion stack.

Solution

We solve the problem by first constructing an adjacency list representing the richer relationships. For each person, we perform a DFS that recursively finds the quietest person among all individuals who are richer. During the DFS, we use memoization to store already computed results to prevent recalculating paths. The DFS function updates the quietest person for the current node by comparing its own quiet value with those returned by its richer neighbors.

Code Solutions

# Python solution with detailed comments
class Solution:
    def loudAndRich(self, richer, quiet):
        # Number of people
        n = len(quiet)
        # Build graph: for each person, track the people who are richer than them
        graph = [[] for _ in range(n)]
        for u, v in richer:
            graph[v].append(u)
        
        # Initialize result array with -1 to denote uncomputed answers
        res = [-1] * n
        
        # DFS function with memoization to determine quietest person for 'person'
        def dfs(person):
            if res[person] != -1:
                return res[person]
            # Start by assuming the person itself is the quietest
            res[person] = person
            # Recursively check all richer people
            for neighbor in graph[person]:
                candidate = dfs(neighbor)
                # If candidate is quieter than the current quietest, update result
                if quiet[candidate] < quiet[res[person]]:
                    res[person] = candidate
            return res[person]
        
        # Run DFS for every person to complete the result
        for p in range(n):
            dfs(p)
        
        return res

# Example usage:
# sol = Solution()
# print(sol.loudAndRich([[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], [3,2,5,4,6,1,7,0]))
← Back to All Questions