The O(n) Club: Find the Town Judge—Or the Search for the Ultimate Influencer

The O(n) Club: Find the Town Judge—Or the Search for the Ultimate Influencer

⚡ TL;DR

You’re looking for the one person in town everyone trusts (n-1 people), who trusts absolutely nobody in return. If that unicorn exists, return their number; otherwise, it’s -1 and your program walks home alone. Forget building charts of suspicious small-town trust. Just score everyone: lose a point if they trust someone, gain a point if they’re trusted. Find the one who ends up with n-1.

// Java quick-and-dirty judge finder
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;

🧠 How Devs Usually Mess This Up

Step 1: Assume trust works like friendship. Nope. This isn’t Facebook—trust is as one-way as a remote control. Step 2: Reward anyone who’s popular, even if they’re also trusting someone else? Oof. The judge doesn’t play favorites, or… anyone. And for those who think the only townie (n=1) can’t be a judge: check the rules. Sometimes you *are* your own jury.

🔍 What’s Actually Going On

Let’s play “Who Wants to Be the Judge?” The crowd puts all their trust tokens onto one person—who sits majestically, pockets zipped, and trusts nobody back. It’s the algorithmic equivalent of a meme god with a million followers and zero following. Mathematically, we assign each person a net trust score: minus one every time they invest trust, plus one every time it’s invested in them. Whoever maxes out at n-1 is probably posting selfies from the judge’s bench.

🛠️ PseudoCode

• Score everyone:
  

  int[] score = new int[n + 1];

  Simple, one-size-fits-all trust scoreboard.

• Process each trust pair:
  

  for (int[] t : trust) {
      score[t[0]]--;
      score[t[1]]++;
  }

  Trusting makes you less judgey. Being trusted? Sweet, one more for your ego.

• Find the judge:
  

  for (int i = 1; i <= n; i++) {
      if (score[i] == n - 1) return i;
  }

  Highest possible score. Not coincidentally, also the person with the most free time.

• No score, no judge:
  

  return -1;

  Spoiler: Most towns are just clusters of disappointment.

💻 The Code

public int findJudge(int n, int[][] trust) {
    if (n == 1 && trust.length == 0) return 1; // Running a one-person judiciary
    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;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• One lonely townie: n = 1 & trust = [] → They’re the judge by default. It’s not sad, it’s optimal.
• Popularity isn’t enough: If the big cheese trusts even one person, they’re toast.
• Remember: No backsies. Trust is directed—no symmetry. If Alice trusts Bob, Bob just shrugs.
• Linear all the way: O(n + m) time, O(n) space. The only thing that’s constant is your caffeine intake.

🧠 Interviewer Brain-Tattoo

“The only true judge trusts absolutely nobody—not even for coffee breaks. Find that person, and you’ve basically hacked society.”