Find the Town Judge

NeetCode: Find the Town Judge · LeetCode: 997. Find the Town Judge · Difficulty: Easy

In a town of n people labeled 1..n there may be a judge. The judge trusts nobody, and everybody else trusts the judge. Given trust, where trust[i] = [a, b] means a trusts b, return the judge's label or -1 if there is none.

Example

Text

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

Brute force: test every candidate against a trust matrix

Record trusts[a][b] in an (n+1) x (n+1) boolean matrix (Java fills a new boolean array with false). For each candidate p, check that p trusts nobody and that every other person trusts p. This is correct but uses quadratic time and space.

Java

class Solution {
    public int findJudge(int n, int[][] trust) {
        boolean[][] trusts = new boolean[n + 1][n + 1];
        for (int[] t : trust) {
            trusts[t[0]][t[1]] = true;
        }
        for (int p = 1; p <= n; p++) {
            boolean trustsNobody = true;
            boolean allTrustP = true;
            for (int q = 1; q <= n; q++) {
                if (trusts[p][q]) trustsNobody = false;
                if (q != p && !trusts[q][p]) allTrustP = false;
            }
            if (trustsNobody && allTrustP) {
                return p;
            }
        }
        return -1;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findJudge(2, new int[][]{{1, 2}}));
        System.out.println(s.findJudge(3, new int[][]{{1, 3}, {2, 3}, {3, 1}}));
        System.out.println(s.findJudge(1, new int[][]{}));
    }
}

Output

2
-1
1

Time: O(n^2). Space: O(n^2).

Optimal: score = trusted-by minus trusts

Give each person a score: +1 each time someone trusts them, -1 each time they trust someone. The judge is trusted by n - 1 people and trusts nobody, so their score is exactly n - 1. No one else can reach that score: anyone who trusts somebody loses a point and is trusted by at most n - 1 others, so their score is at most n - 2. One pass over trust and one scan of the scores suffice. Scores are at most n in magnitude, so int cannot overflow.

Java

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] score = new int[n + 1];
        for (int[] t : trust) {
            score[t[0]]--;
            score[t[1]]++;
        }
        for (int p = 1; p <= n; p++) {
            if (score[p] == n - 1) {
                return p;
            }
        }
        return -1;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findJudge(2, new int[][]{{1, 2}}));
        System.out.println(s.findJudge(3, new int[][]{{1, 3}, {2, 3}, {3, 1}}));
        System.out.println(s.findJudge(1, new int[][]{}));
    }
}

Output

2
-1
1

Time: O(n + t) for t trust pairs. Space: O(n).