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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Loud and Rich

Difficulty: Medium

Problem Description

Given a group of n people, each with different amounts of money and levels of quietness, you need to determine for each person the quietest person who has equal to or more money than them based on the provided relationships of wealth.

Key Insights

  • The problem can be represented as a directed graph where each person is a node and an edge from person A to person B indicates that A is richer than B.
  • We can use Depth-First Search (DFS) or Topological Sort to explore the graph and determine the quietest person among those who are richer or equally rich.
  • Each person's quietness is unique, allowing us to easily identify the quietest person in each connected component of the graph.

Space and Time Complexity

Time Complexity: O(n + m) where n is the number of people and m is the number of relations in the richer array.
Space Complexity: O(n + m) for storing the graph and the answer array.

Solution

To solve the problem, we will:

  1. Construct a directed graph from the richer relationships.
  2. Use DFS to explore the graph starting from each node (person).
  3. During the exploration, keep track of the quietest person encountered.
  4. Store the results in an answer array where each index corresponds to a person, and the value is the index of the quietest person among those who are richer or equally rich.

Code Solutions

def loudAndRich(richer, quiet):
    from collections import defaultdict
    
    # Create graph
    graph = defaultdict(list)
    for a, b in richer:
        graph[a].append(b)
        
    n = len(quiet)
    answer = [-1] * n
    
    def dfs(node):
        if answer[node] != -1:
            return answer[node]
        
        answer[node] = node  # Initially, the quietest person is themselves
        for neighbor in graph[node]:
            # Find the quietest person among neighbors
            quietest = dfs(neighbor)
            if quiet[quietest] < quiet[answer[node]]:
                answer[node] = quietest
        
        return answer[node]
    
    for i in range(n):
        dfs(i)
    
    return answer
← Back to All Questions