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 <= 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]'s are all different.
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
}