Find the Town Judge

Problem#

In a town with n people, the judge trusts no one and is trusted by everyone else. Given a list of trust edges [a, b] meaning a trusts b, return the judge’s label, or -1 if no such person exists.

Examples#

n = 2, trust = [[1,2]] → 2
n = 3, trust = [[1,3],[2,3]] → 3
n = 3, trust = [[1,3],[2,3],[3,1]] → -1

Constraints#

1 <= n <= 1000, 0 <= trust.length <= 10^4.

Approach#

For each trust [a, b], decrement score[a] and increment score[b]. The judge will end with score n - 1.

Solution#

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> score(n + 1, 0);
        for (auto& t : trust) {
            score[t[0]]--;
            score[t[1]]++;
        }
        for (int i = 1; i <= n; ++i)
            if (score[i] == n - 1) return i;
        return -1;
    }
};

func findJudge(n int, trust [][]int) int {
    score := make([]int, n+1)
    for _, t := range trust {
        score[t[0]]--
        score[t[1]]++
    }
    for i := 1; i <= n; i++ {
        if score[i] == n-1 {
            return i
        }
    }
    return -1
}

from typing import List

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        score = [0] * (n + 1)
        for a, b in trust:
            score[a] -= 1
            score[b] += 1
        for i in range(1, n + 1):
            if score[i] == n - 1:
                return i
        return -1

var findJudge = function(n, trust) {
    const score = new Array(n + 1).fill(0);
    for (const [a, b] of trust) {
        score[a]--;
        score[b]++;
    }
    for (let i = 1; i <= n; i++) {
        if (score[i] === n - 1) return i;
    }
    return -1;
};

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 i = 1; i <= n; i++) {
            if (score[i] == n - 1) return i;
        }
        return -1;
    }
}

function findJudge(n: number, trust: number[][]): number {
    const score: number[] = new Array(n + 1).fill(0);
    for (const [a, b] of trust) {
        score[a]--;
        score[b]++;
    }
    for (let i = 1; i <= n; i++) {
        if (score[i] === n - 1) return i;
    }
    return -1;
}

Editorial#

Net score collapses in-degree and out-degree into one counter. The judge has +1 from every other person (n - 1) and 0 outgoing (no -1). Nobody else can reach n - 1 because at minimum, they trust someone (the judge), costing them -1.

Complexity#

Time: O(n + E).
Space: O(n).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#