algoadvance

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] = [a, b] representing that person a trusts person b.

Return the label of the town judge if the town judge exists and can be identified. Otherwise, return -1.

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

Clarifying Questions

  1. What if the trust array is empty and n > 1?
    • If trust is empty and n > 1, it means that no one trusts anyone. Hence, there can’t be a judge, as the judge needs at least n-1 people to trust them.
  2. What if n == 1?
    • If n == 1, the single person is trivially the judge as there is no one else in the town.

Strategy

We can use a degree counting approach to solve this problem:

  1. Create two arrays trusts and trusted_by of size n+1 to count how many people each person trusts and how many people trust each person, respectively.
  2. Iterate through the trust array and populate these arrays.
  3. The town judge will be the person i with trusts[i] == 0 and trusted_by[i] == n-1.

Code

def findJudge(n, trust):
    if n == 1:
        return 1

    trusts = [0] * (n + 1)
    trusted_by = [0] * (n + 1)
    
    for a, b in trust:
        trusts[a] += 1
        trusted_by[b] += 1

    for i in range(1, n + 1):
        if trusts[i] == 0 and trusted_by[i] == n - 1:
            return i

    return -1

Time Complexity

This solution is efficient and should handle the input constraints well. If you have any specific edge cases or further questions, feel free to ask!

Try our interview co-pilot at AlgoAdvance.com