Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/851.html

851. Loud and Rich

Level

Medium

Description

In a group of N people (labelled 0, 1, 2, ..., N-1), each person has different amounts of money, and different levels of quietness.

For convenience, we’ll call the person with label x, simply “person x”.

We’ll say that richer[i] = [x, y] if person x definitely has more money than person y. Note that richer may only be a subset of valid observations.

Also, we’ll say quiet[x] = q if person x has quietness q.

Now, return 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 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 isn’t 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.

Note:

  1. 1 <= quiet.length = N <= 500
  2. 0 <= quiet[i] < N, all quiet[i] are different.
  3. 0 <= richer.length <= N * (N-1) / 2
  4. 0 <= richer[i][j] < N
  5. richer[i][0] != richer[i][1]
  6. richer[i]’s are all different.
  7. The observations in richer are all logically consistent.

Solution

Use the idea of breadth first search. First, for each person, obtain all the people that is definitely poorer than the person, and use a set to store all richest person, which means that a person is in the set if and only if there is no observation that shows that the person is poorer than any other person. Then create the result array answer and initialize answer[i] = i for 0 <= i < N. Next, starting from the elements in the set, do breadth first search. For each person, if there exists a richer person of the person with lower quietness, then update the current person’s value in the result array. Finally, return the result array.

  • class Solution {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        Map<Integer, Set<Integer>> poorerMap = new HashMap<Integer, Set<Integer>>();
        Set<Integer> set = new HashSet<Integer>();
        for (int[] curRicher : richer) {
            int person1 = curRicher[0], person2 = curRicher[1];
            Set<Integer> poorerSet = poorerMap.getOrDefault(person1, new HashSet<Integer>());
            poorerSet.add(person2);
            poorerMap.put(person1, poorerSet);
            set.add(person1);
            set.remove(person2);
        }
        int length = quiet.length;
        int[] answer = new int[length];
        for (int i = 0; i < length; i++)
            answer[i] = i;
        while (!set.isEmpty()) {
            Set<Integer> prevSet = new HashSet<Integer>(set);
            set.clear();
            for (int person1 : prevSet) {
                int answer1 = answer[person1];
                Set<Integer> poorerSet = poorerMap.getOrDefault(person1, new HashSet<Integer>());
                for (int person2 : poorerSet) {
                    int answer2 = answer[person2];
                    if (quiet[answer1] < quiet[answer2])
                        answer[person2] = answer[person1];
                    set.add(person2);
                }
            }
        }
        return answer;
    }
}

  • // OJ: https://leetcode.com/problems/loud-and-rich/
// Time: O(N + E)
// Space: O(N + E)
class Solution {
public:
    vector<int> loudAndRich(vector<vector<int>>& R, vector<int>& Q) {
        int N = Q.size();
        vector<vector<int>> G(N);
        vector<int> indegree(N);
        for (auto &r : R) {
            int u = r[0], v = r[1];
            G[u].push_back(v);
            indegree[v]++;
        }
        queue<int> q;
        vector<int> ans(N), minQuite(N, INT_MAX);
        for (int i = 0; i < N; ++i) {
            minQuite[i] = Q[i];
            ans[i] = i;
            if (indegree[i] == 0) q.push(i);
        }
        while (q.size()) {
            auto u = q.front();
            q.pop();
            for (int v : G[u]) {
                if (minQuite[u] < minQuite[v]) {
                    ans[v] = ans[u];
                    minQuite[v] = minQuite[u];
                }
                if (--indegree[v]) continue;
                q.push(v);
            }
        }
        return ans;
    }
};

  • class Solution:
    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
        n = len(quiet)
        g = defaultdict(list)
        for a, b in richer:
            g[b].append(a)
        ans = [-1] * n

        def dfs(i):
            if ans[i] != -1:
                return
            ans[i] = i
            for j in g[i]:
                dfs(j)
                if quiet[ans[j]] < quiet[ans[i]]:
                    ans[i] = ans[j]

        for i in range(n):
            dfs(i)
        return ans

############

class Solution:
    def loudAndRich(self, richer, quiet):
        """
        :type richer: List[List[int]]
        :type quiet: List[int]
        :rtype: List[int]
        """
        m = collections.defaultdict(list)
        for i, j in richer:
            m[j].append(i)
        
        res = [-1] * len(quiet)
        
        def dfs(i):
            if res[i] > 0: return res[i]
            res[i] = i
            for j in m[i]:
                if quiet[res[i]] > quiet[dfs(j)]:
                    res[i] = res[j]
            return res[i]

        for i in range(len(quiet)):
            dfs(i)
        return res

  • func loudAndRich(richer [][]int, quiet []int) []int {
    n := len(quiet)
    ans := make([]int, n)
    g := make([][]int, n)
    for i := 0; i < n; i++ {
        ans[i] = -1
        g[i] = make([]int, 0)
    }
    for _, r := range richer {
        g[r[1]] = append(g[r[1]], r[0])
    }

    var dfs func(i int)
    dfs = func(i int) {
        if ans[i] != - 1 {
            return
        }
        ans[i] = i
        for _, j := range g[i] {
            dfs(j)
            if quiet[ans[j]] < quiet[ans[i]] {
                ans[i] = ans[j]
            }
        }
    }

    for i := 0; i < n; i++ {
        dfs(i)
    }
    return ans
}

All Problems

All Solutions