[leetcode #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:

1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. 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 <= 10⁴
・ trust[i].length == 2
・ All the pairs of trust are unique.
・ aᵢ != bᵢ
・ 1 <= aᵢ, bᵢ <= n

Idea

마을에 있는 재판관이 누구인지 찾는 문제다.

재판관은 마을 누구도 신뢰하지 않아야 하며, 자기를 제외한 모든 이들의 신뢰를 받아야 한다.

주어진 trust를 탐색하면서 마을 사람들의 신뢰 여부와 신뢰받는 수를 계산한다.
신뢰 여부를 확인하면서 누구도 신뢰하지 않는 사람을 찾고, 그 사람이 신뢰받는 수가 n-1인지 확인하면 된다. 이 조건에 해당하는 사람이 재판관이며, n-1이 아닌 경우에는 -1을 리턴한다.

Solution

class Solution {
    public int findJudge(int n, int[][] trust) {
        boolean[] havingTrust = new boolean[n+1];
        int[] trustCount = new int[n+1];

        for (int i=0; i < trust.length; i++) {
            havingTrust[trust[i][0]] = true;
            trustCount[trust[i][1]]++;
        }

        int candidate = 0;
        for (int i=1; i <= n; i++) {
            if (!havingTrust[i]) {
                candidate = i;
                break;
            }
        }

        if (trustCount[candidate] != n-1) {
            return -1;
        }

        return candidate;
    }
}

Reference

https://leetcode.com/problems/find-the-town-judge/