Find the Town Judge

easy graph hash map

Problem

Given n people (1..n) and a list of trust pairs [a, b] meaning a trusts b, return the town judge (trusted by everyone, trusts no one) or -1.

Inputn=3, trust=[[1,3],[2,3]]

Output3

score[b]++ and score[a]−−; judge has score n − 1.

trust (a-b, comma list)

def findJudge(n, trust):
    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

function findJudge(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;
    }
}

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;
}

Explanation

The town judge is the one person who is trusted by everyone else but trusts nobody. Instead of building a graph, we can spot them with a single score counter per person.

We keep score[i] that goes up when someone trusts i and down when i trusts someone. For each trust pair [a, b] we do score[a]-- (a trusts somebody) and score[b]++ (b is trusted).

Now think about the judge: they are trusted by all n - 1 other people (so +(n-1)) and trust no one (so 0 deductions). That gives them a final score of exactly n - 1. Nobody else can hit this value, because trusting even one person knocks their score below the maximum.

Example: n = 3, trust [[1,3],[2,3]]. Person 3 gets +2 and never trusts anyone, ending at score 2 = n - 1, while persons 1 and 2 end at -1. So the judge is 3.

We finish by scanning everyone for the one whose score equals n - 1, returning that index, or -1 if no one qualifies.

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