The O(n) Club: Find the Town Judge (LeetCode 997) — Java Edition for Trust Issues

The O(n) Club: Find the Town Judge (LeetCode 997) — Java Edition for Trust Issues

⚡ TL;DR

This problem is about sniffing out that one person who’s so aloof, they trust nobody, yet everyone trusts them. It’s like finding a celebrity at a party—except instead of selfies, you’re passing Java arrays. Naive brute force? Enjoy your O(n^2) headache. But with a single counter array, you’ll solve this before the party snacks run out!

// Core Java snippet
for (int[] t : trust) {
    netTrust[t[0]]--;
    netTrust[t[1]]++;
}
// Your judge is netTrust[i] == n-1

🧠 How Devs Usually Mess This Up

Let’s be honest—most devs see trust[i] = [a, b] and instantly forget which way trust flows. (No judgment, just facts.) Some write code as if b trusts a, which is the algorithmic equivalent of putting both shoes on your left foot. Others check every combination, turning O(n) logic into O(hair loss). And the best: assuming every town MUST have a judge. Sorry, sometimes it’s just chaos out there.

🔍 What’s Actually Going On

Picture this: a town full of gossips, and one mysterious individual nobody’s ever seen with a friend, yet the entire population swears by them. That, my friends, is your ‘judge’. In graph-speak, you want outdegree 0 (trusts no one) and indegree n-1 (trusted by everyone else). Track each person’s “net trust score”: lose points for trusting, gain for being trusted. One loop—done.

🛠️ PseudoCode

• Create netTrust array, size n+1 (LeetCode loves 1-indexed misery).
• For each trust pair [a, b]:
  • netTrust[a] -= 1; // a trusts someone—not judge material
  • netTrust[b] += 1; // b is trusted—possible judge
• Loop i = 1 to n:
  • If netTrust[i] == n-1, return i (congrats, you found the star of Judge Judy: LeetCode edition)
• No candidates? Return -1 (yep, town’s a mess)

💻 The Code

public int findJudge(int n, int[][] trust) {
    if (n == 1 && trust.length == 0) return 1; // Solo? Insta-judge.
    int[] netTrust = new int[n + 1];
    for (int[] t : trust) {
        netTrust[t[0]]--;
        netTrust[t[1]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (netTrust[i] == n - 1) return i;
    }
    return -1; // Anarchy wins today.
}

⚠️ Pitfalls, Traps & Runtime Smacks

• 1-person edge case? The lone villager IS the judge (awkward, but true).
• Trust flow direction? Yes, trust[i] = [a, b] means a trusts b—don’t swap it, or your code will cosplay as buggy Dijkstra’s.
• Not every town has a judge. If nobody fits, return -1. No consolation prizes, no democracy.
• Time/Space? O(n + m), and cleaner than any full adjacency matrix you would’ve regretted making.

🧠 Interviewer Brain-Tattoo

“If everyone likes you and you trust nobody, congrats—either you’re the town judge or you just deleted LinkedIn.”