</>Ali · LeetCode
#0997·EasyGraphs

Find the Town Judge

LeetCode #997 · Easy · Graphs · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Indegree and Outdegree Count

Key insight

Model this as a directed graph problem where trust[i] = [a, b] represents an edge from a to b. The town judge is the node with: - Indegree = n - 1 (everyone trusts them) - Outdegree = 0 (they trust nobody)

Strategy

  1. 1Build indegree and outdegree arrays for all n people
  2. 2For each trust relationship [a, b]:
  3. 3Find the person with indegree = n-1 and outdegree = 0
Time
O(T + n)
T = trust.length
Space
O(n)
two arrays of size n+1
Problem description(from LeetCode)

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: 1. The town judge trusts nobody. 2. Everybody (except for the town judge) trusts the town judge. 3. There is exactly one person that satisfies properties 1 and 2. You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi. If a trust relationship does not exist in trust array, then such a trust relationship does not exist. Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Examples

Example 1
Input:
n = 2, trust = [[1,2]]
Output:
2

Constraints

  • •1 <= n <= 1000
  • •0 <= trust.length <= 10^4
  • •trust[i].length == 2
  • •All the pairs of trust are unique.
  • •ai != bi
  • •1 <= ai, bi <= n

C++ Solution

solution.cpp
class Solution {
public:
int findJudge(int n, vector<vector<int>> &trust) {
    vector<int> indegree(n + 1, 0);
    vector<int> outdegree(n + 1, 0);

    for (auto trustItem : trust) {
      outdegree[trustItem[0]]++;
      indegree[trustItem[1]]++;
    }

    for (int i = 1; i <= n; i++) {
      if (indegree[i] == n - 1 && outdegree[i] == 0) {
        return i;
      }
    }

    return -1;
  }

  /*
   * Approach 2: Single Array (Net Trust Score)
   *
   * Key Insight: Instead of tracking indegree and outdegree separately,
   * use a single "trust score" where:
   * - Being trusted adds +1
   * - Trusting someone adds -1
   *
   * The judge will have a net score of exactly n - 1.
   *
   * Time Complexity: O(T + n) where T = trust.length
   * Space Complexity: O(n) - single array of size n+1
   */
  int findJudgeOptimized(int n, vector<vector<int>> &trust) {
    vector<int> trustScore(n + 1, 0);

    for (const auto &t : trust) {
      trustScore[t[0]]--; // Trusts someone, loses a point
      trustScore[t[1]]++; // Is trusted, gains a point
    }

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

    return -1;
  }
};

More Graphs problems