997. Find the Town Judge #

Problem #

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

• The town judge trusts nobody.
• Everybody (except for the town judge) trusts the town judge.
• There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Example 1:

Input: n = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Constraints:

• 1 <= n <= 1000
• 0 <= trust.length <= 10000
• trust[i].length == 2
• All the pairs of trust are unique.
• ai != bi
• 1 <= ai, bi <= n

Problem Summary #

There are n people in a town, labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge really exists, then:

• The town judge does not trust anyone.
• Everyone (except the town judge) trusts this town judge.
• Exactly one person satisfies both property 1 and property 2.

You are given an array trust, where trust[i] = [ai, bi] means that the person labeled ai trusts the person labeled bi.

If the town judge exists and their identity can be determined, return the judge’s label; otherwise, return -1.

Solution Approach #

Count in-degrees and out-degrees

• Being trusted by others is defined as in-degree, and trusting others is defined as out-degree
• If there is a number x between 1 and n whose in-degree is n - 1 and out-degree is 0, return x

Code #

package leetcode

func findJudge(n int, trust [][]int) int {
	if n == 1 && len(trust) == 0 {
		return 1
	}
	judges := make(map[int]int)
	for _, v := range trust {
		judges[v[1]] += 1
	}
	for _, v := range trust {
		if _, ok := judges[v[0]]; ok {
			delete(judges, v[0])
		}
	}
	for k, v := range judges {
		if v == n-1 {
			return k
		}
	}
	return -1
}