851. Loud and Rich

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] = [ai, bi] indicates that ai has more money than bi and an integer array quiet where quiet[i] is the quietness of the ith 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.

• Time : O(n)
• Space : O(n)

class Solution {
    vector<pair<int,int>> memo;
    unordered_map<int, vector<int>> topology;
    
    pair<int, int> solution(int i, vector<int>& q) {
        if(memo[i].first != -1) return memo[i];
        auto& res = memo[i] = {i, q[i]};

        for(auto moreMoney : topology[i]) {
            auto [person, quite] = solution(moreMoney, q);
            if(quite < res.second) {
                res = {person, quite};
            }
        }
        return res;
    }
public:
    vector<int> loudAndRich(vector<vector<int>>& r, vector<int>& q) {
        memo = vector<pair<int,int>>(q.size(), {-1,-1});
        vector<int> res(q.size(), -1);
        for(auto& vec : r) {
            topology[vec[1]].push_back(vec[0]);
        }

        for(int i = 0; i < q.size(); i++) {
            auto [person, _] = solution(i, q);
            res[i] = person;
        }

        return res;
    }
};