Find the Town Judge

EASY✓ CHIP-TIMEDLC #997 — FULL STATEMENT ↗

The drill: Among n townspeople labeled 1 through n, each [a, b] entry means a trusts b. Find the person that every other townsperson trusts while trusting no one back — the town judge — or report −1 if no one fits.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A town of n people, numbered 1 through n, has a list of trust statements shaped [a, b], meaning person a trusts person b. Somewhere in that town might sit a judge: someone every other person trusts, who trusts nobody in return.

The judge, if one exists, is unique — there's exactly one person satisfying both conditions or nobody does. Trust statements don't include self-trust, and a pair can't repeat, so the raw list is enough to work from directly.

The answer is that person's number, or −1 if no single townsperson trusts nobody while being trusted by literally everyone else.

EX 01

n = 2 · trust = [[1, 2]]

→ 2

ONE TRUSTS THE OTHER

EX 02

n = 1 · trust = []

→ 1

SINGLE PERSON IS TRIVIALLY THE JUDGE

EX 03

n = 3 · trust = [[1, 3], [2, 3]]

→ 3

TRUSTED BY EVERYONE ELSE

1 to a few thousand townspeople
trust list length scales with the number of people, not fixed
no person trusts themselves, and no trust pair repeats
at most one judge can exist — never a tie between two people

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Only two facts about a person matter: how many people trust them, and how many people they trust. What must those two numbers look like for the judge?

HINT 2 THE STRUCTURE

The judge is trusted by everyone else (n−1 incoming trusts) and trusts nobody (zero outgoing trusts). A single running score per person — trusted-count minus trusts-count — captures both at once.

HINT 3 ONE STEP FROM THE ANSWER

For each pair [a, b], add 1 to b's score and subtract 1 from a's score. The judge, if one exists, is the only person left with a score of exactly n−1.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE NET SCOREPATTERN · ONE SCORE ARRAYn = 4 people · trust: 1→3, 1→4, 2→3, 2→4, 4→3

STEP 1

Score = trusted-count minus trusts-count. Every [a,b] pair does score[a]-1, score[b]+1. The judge ends at exactly n−1 = 3.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/find-the-town-judge.py — RACE PACE

LANG ▸

PACE ▸

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 person in range(1, n + 1):
            if score[person] == n - 1:
                return person
        return -1

TIME O(N+M)SPACE O(N)PYTHON · RACE PACE · 10 LN

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        for candidate in range(1, n + 1):
            trusts_anyone = False
            trusted_by = 0
            for a, b in trust:
                if a == candidate:
                    trusts_anyone = True
                if b == candidate:
                    trusted_by += 1
            if not trusts_anyone and trusted_by == n - 1:
                return candidate
        return -1

TIME O(N·M)SPACE O(1)PYTHON · TRAINING PACE · 13 LN

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

TIME O(N+M)SPACE O(N)JAVA · RACE PACE · 13 LN

class Solution {
    public int findJudge(int n, int[][] trust) {
        for (int candidate = 1; candidate <= n; candidate++) {
            boolean trustsAnyone = false;
            int trustedBy = 0;
            for (int[] pair : trust) {
                if (pair[0] == candidate) trustsAnyone = true;
                if (pair[1] == candidate) trustedBy++;
            }
            if (!trustsAnyone && trustedBy == n - 1) return candidate;
        }
        return -1;
    }
}

TIME O(N·M)SPACE O(1)JAVA · TRAINING PACE · 14 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED