851. Loud and Rich

Problem

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 = q if person x has quietness q.

Now, return answer, where answer = 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.

Problem Summary

In a group of N people (numbered 0, 1, 2, ..., N-1), each person has a different amount of money and a different level of quietness. For convenience, we refer to the person numbered x as "person x ". If we can be certain that person x has more money than person y, we say richer[i] = [x, y] . Note that richer may be only a subset of valid observations. Also, if person x has quietness level q , we say quiet[x] = q . Now, return the answer answer , where answer[x] = y means that among all people who have no less money than person x , person y is the quietest person (that is, the person with the smallest quietness value quiet[y] ).

Notes:

• 1 <= quiet.length = N <= 500
• 0 <= quiet[i] < N, all quiet[i] are different.
• 0 <= richer.length <= N * (N-1) / 2
• 0 <= richer[i][j] < N
• richer[i][0] != richer[i][1]
• richer[i] are all different.
• The observations in richer are logically consistent.

Solution Approach

• Given 2 arrays, richer and quiet, output answer, where answer = y means that among all people who have no less money than x, y is the quietest person (that is, the person with the smallest quietness value quiet[y]).
• From the problem statement, we know that richer forms a directed acyclic graph. First, use a dictionary to build the graph relationships and find all people who are richer than the current index. Then use breadth-first level-order traversal, continuously using richer people with smaller quietness values to update their child nodes.
• This problem can also be solved using topological sorting. Treat the relationships described in richer as edges; if x > y, then x points to y. Treat quiet as weights. Use an array to record the answer, initially with ans[i] = i. Then perform topological sorting on the original graph. For each edge, if quiet[ans[v]] > quiet[ans[u]], then the answer for ans[v] is ans[u]. The time complexity is the time complexity of topological sorting, O(m+n). The space complexity requires an O(m) array to build the graph, and O(n) arrays to record indegrees and store the queue, so the space complexity is O(m+n).

Code

func loudAndRich(richer [][]int, quiet []int) []int {
	edges := make([][]int, len(quiet))
	for i := range edges {
		edges[i] = []int{}
	}
	indegrees := make([]int, len(quiet))
	for _, edge := range richer {
		n1, n2 := edge[0], edge[1]
		edges[n1] = append(edges[n1], n2)
		indegrees[n2]++
	}
	res := make([]int, len(quiet))
	for i := range res {
		res[i] = i
	}
	queue := []int{}
	for i, v := range indegrees {
		if v == 0 {
			queue = append(queue, i)
		}
	}
	for len(queue) > 0 {
		nexts := []int{}
		for _, n1 := range queue {
			for _, n2 := range edges[n1] {
				indegrees[n2]--
				if quiet[res[n2]] > quiet[res[n1]] {
					res[n2] = res[n1]
				}
				if indegrees[n2] == 0 {
					nexts = append(nexts, n2)
				}
			}
		}
		queue = nexts
	}
	return res
}