Find the Town Judge

Problem Statement:

In a town, there are N people labelled 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 trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.

If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.

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

Example 4:

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

Example 5:

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3

Note:

1. 1 <= N <= 1000
2. trust.length <= 10000
3. trust[i] are all different
4. trust[i][0] != trust[i][1]
5. 1 <= trust[i][0], trust[i][1] <= N

Solution:

Sounds very simple problem but I found it tricky if you don't see those.

1. First, we need to find who trust who. Remember the judge does not trust anybody but everybody trust just. If A trust B, D trust B, and C trust B so B is the judge. We can use a map to find a possible judge.

B-> A,D,C

Here B is the key(possible judge) and ADC is the person who trusts B is the judge.

2. To avoid cycle, use an extra array to find the relation that judge trust someone or not.

public class TownJudge {
    TownJudge townJudge;

    @BeforeEach
    public void init() {
        townJudge = new TownJudge();
    }

    @Test
    public void townJudgeFirstPositive() {
        int res = townJudge.findJudge(4, new int[][]{{1, 3}, {1, 4}, {2, 3}, {2, 4}, {4, 3}});
        Assertions.assertEquals(3, res);
    }

    @Test
    public void townJudgeSecondPositive() {
        int res = townJudge.findJudge(2, new int[][]{{1, 2}, {2, 3}});
        Assertions.assertEquals(-1, res);
    }

    @Test
    public void townJudgeThirdPositive() {
        int res = townJudge.findJudge(3, new int[][]{{1, 3}, {2, 3}, {3, 1}});
        Assertions.assertEquals(-1, res);
    }

    @Test
    public void townJudgeFourthPositive() {
        int res = townJudge.findJudge(3, new int[][]{{1, 3}, {2, 3}});
        Assertions.assertEquals(3, res);
    }

    @Test
    public void townJudgeFifthPositive() {
        int res = townJudge.findJudge(4, new int[][]{{1, 2}, {1, 3}, {2, 1}, {2, 3}, {1, 4}, {4, 3}, {4, 1}});
        Assertions.assertEquals(3, res);
    }

    public int findJudge(int N, int[][] trust) {
        if (trust.length == 0) return 1;
        /**
         * Simple parents tracker
         * */
        int[] parents = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            parents[i] = i;
        }
        /**
         * Extracting the possible town judge
         * */
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int[] data : trust) {
            int a = data[0];
            int b = data[1];
            parents[a] = b;
            map.computeIfAbsent(b, val -> new ArrayList<>()).add(a);
        }

        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry e = (Map.Entry) it.next();
            ArrayList<Integer> members = (ArrayList<Integer>) e.getValue();
            if (members.size() == N - 1) { //all the citizen except the judge
                int key = (int) e.getKey();
                if (parents[key] != key) return -1;// if judge trust someone else
                return (int) e.getKey();
            }
        }
        return -1;
    }
}

Code can be found here.