algoadvance

Leetcode 851. Loud and Rich

Problem Statement

In a group of n people (labelled from 0 to n - 1), each person has a different amount of money, and a different level of quietness.

For the purposes of this problem, we will use richer[i] = [x, y] to say that person x is richer than person y. Notice that richer may only provide information about some of the people.

Also, we’ll use quiet[i] to represent the quietness of the person i. All the quietness values are unique.

Return an integer array answer where answer[i] = x means that person x has the least quietness among all people who definitely have equal to or more money than the person i.

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 (with quietness 1) is person 5.

Example 2:

Input: richer = [], quiet = [0]
Output: [0]

Clarifying Questions

  1. Can there be multiple richer relationships for a single person?
    • Yes, a single person can have multiple richer relationships.
  2. What is the range for n (number of people)?
    • Typically, n is within the range of 1 to 500.
  3. Are there any constraints on the elements in quiet?
    • Yes, all the values in quiet are unique.

Strategy

  1. Graph Representation:
    • Represent the richer relationship as a directed graph where an edge from x to y indicates x is richer than y.
  2. Finding the Answer:
    • Use Depth-First Search (DFS) to determine the person with the smallest quietness value for each person considering all richer relationships.
  3. Memoization:
    • Use memoization to avoid recalculating the answer for a person multiple times.

Code

#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
        int n = quiet.size();
        vector<vector<int>> graph(n);
        
        for (const auto& pair : richer) {
            graph[pair[1]].push_back(pair[0]);
        }
        
        vector<int> answer(n, -1);
        
        for (int i = 0; i < n; ++i) {
            dfs(graph, quiet, answer, i);
        }
        
        return answer;
    }
    
private:
    int dfs(vector<vector<int>>& graph, vector<int>& quiet, vector<int>& answer, int person) {
        if (answer[person] != -1) {
            return answer[person];
        }
        
        int minQuietPerson = person;
        for (int richerPerson : graph[person]) {
            int cand = dfs(graph, quiet, answer, richerPerson);
            if (quiet[cand] < quiet[minQuietPerson]) {
                minQuietPerson = cand;
            }
        }
        
        answer[person] = minQuietPerson;
        return minQuietPerson;
    }
};

Time Complexity

The provided code should efficiently solve the problem by leveraging graph traversal and memoization.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI