{x}
blog image

Find the Town Judge

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.

 

Example 1:

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

Example 2:

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

Example 3:

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

 

Constraints:

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

Solution Explanation: Finding the Town Judge

This problem asks to identify the town judge given a list of trust relationships between people in a town. The town judge is a unique person who is trusted by everyone except themselves and trusts no one.

Approach: Using Two Count Arrays

The most efficient approach leverages two arrays to track trust relationships:

  1. inDegree (or cnt1 in the code): Stores the number of people each person trusts. This represents the outgoing edges of the trust graph. A town judge would have an inDegree of 0.

  2. outDegree (or cnt2 in the code): Stores the number of people who trust each person. This represents the incoming edges of the trust graph. A town judge would have an outDegree of n-1 (where n is the number of people).

The algorithm proceeds as follows:

  1. Initialization: Create two arrays, inDegree and outDegree, both of size n+1 and initialized to 0. We use n+1 because person IDs are 1-indexed.

  2. Counting Trusts: Iterate through the trust array. For each [a, b], increment inDegree[a] (person a trusts person b) and increment outDegree[b] (person b is trusted by person a).

  3. Finding the Judge: Iterate from 1 to n. If a person i has inDegree[i] == 0 and outDegree[i] == n - 1, then that person is the town judge.

  4. No Judge: If no such person is found, return -1.

Time and Space Complexity

  • Time Complexity: O(n + t), where n is the number of people and t is the number of trust relationships. The algorithm iterates through the trust array once and then iterates through the people once.

  • Space Complexity: O(n). The space used is dominated by the inDegree and outDegree arrays, both of size n+1.

Code Examples (Python, Java, C++, Go, TypeScript, Rust)

The code examples in the different programming languages demonstrate the same approach. The core logic involves the two counting arrays and the final check for the conditions of the town judge. Each example accurately reflects the algorithm and adheres to the specified complexity bounds. The comments within the code further clarify the purpose of each step.

Example Walkthrough

Let's consider n = 3, trust = [[1,3],[2,3]].

  1. inDegree is initialized to [0, 0, 0, 0].
  2. outDegree is initialized to [0, 0, 0, 0].
  3. After processing trust, inDegree becomes [0, 0, 1, 1] (person 1 trusts 3 and person 2 trusts 3).
  4. outDegree becomes [0, 0, 0, 2] (person 3 is trusted by 1 and 2).
  5. The loop checks:
    • inDegree[1] != 0 so 1 is not the judge.
    • inDegree[2] != 0 so 2 is not the judge.
    • inDegree[3] == 0 and outDegree[3] == 2 == 3 - 1, so 3 is the judge.
  6. The function returns 3.

This approach efficiently determines the town judge using a linear scan, making it optimal for this problem.