LintCode 1449 · Loud and Rich.java

	// Approach #1 - DFS + Memoization - Build Graph w/ adjacency list.
	// T O(n + edges + n * edges) = T O(n * edges), given that n is the length of quiet (# of people). h is the parent edges of the graph (worse case h = n).
	public class Solution {
	/**
	* @param richer: the richer array
	* @param quiet: the quiet array
	* @return: the answer
	*/
	public int[] loudAndRich(int[][] richer, int[] quiet) {
	// handle corner cases
	if (quiet == null || quiet.length == 0) {
	return quiet;
	}
	if (richer == null || richer.length == 0) {
	answer = new int[quiet.length];
	for (int i = 0; i < quiet.length; i++) {
	answer[i] = i;
	}
	return answer;
	}
	int n = quiet.length;
	answer = new int[n];
	Arrays.fill(answer, -1);
	// step #1 build graph - with adjacency list. T O(n + edges)
	List<Integer>[] graph = new ArrayList[n];
	// fill the list. T O(n)
	for (int person = 0; person < n; person++) {
	graph[person] = new ArrayList<>();
	}
	// add the edges into the adjacency list. T O(edges)
	for (int[] edge : richer) {
	graph[edge[1]].add(edge[0]);
	}
	// Step #2 foreach person, find the (dfs direct/ in-direct) smallest quiet. T O(n * h)
	for (int person = 0; person < n; person++) {
	answer[person] = dfs(graph, quiet, person);
	}
	return answer;
	}
	private int[] answer;
	private int dfs(List<Integer>[] graph, int[] quiet, int person) {
	// find the (dfs direct/ in-direct) max quiet
	if (answer[person] != -1) {
	return answer[person];
	}
	// init with himself
	answer[person] = person;
	// search for quieter (from the richer persons)
	for (int richer : graph[person]) { // foreach richer, find quieter
	int quietest = dfs(graph, quiet, richer);
	if (quiet[quietest] < quiet[answer[person]]) {
	answer[person] = quietest;
	}
	}
	return answer[person];
	}
	}

view raw LintCode 1449 · Loud and Rich.java hosted with ❤ by GitHub