Find the Town Judge

Patrick Leaton
Published: Oct. 16, 2021, 2 p.m.
Problem Description

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.

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

Example 4:

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

Example 5:

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

 

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

 

The description was taken from https://leetcode.com/problems/find-the-town-judge/.

Problem Solution

#O(V+E) Time, O(V+E) Space
class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if len(trust) < n - 1:
            return -1
       
        adjacency = collections.defaultdict(list)
        seen = collections.defaultdict(int)
       
        for node, neighbor in trust:
            adjacency[node].append(neighbor)
            seen[neighbor] += 1
           
        for node in range(1, n+1):
            if not adjacency[node] and seen[node] == n-1:
                return node
       
        return -1

Problem Explanation

The input is given to us as a list of edges between nodes, a list of trusts between people.

In order to solve this, we can make an adjacency list to create a graph.  Once we have done that, we will look for the node that has no child nodes and that has been seen as a child in each other nodes' adjacency list.

If that node doesn't exist, we will return a negative one.

Starting off, if the edges list is less than the number of nodes minus one, then each node can't be connected.  A graph with three nodes would have two edges to connect them, for example.

If that is the case, we will return a negative one because the judge would need to have a connection with everybody else.

        if len(trust) < n - 1:
            return -1

 

Otherwise, we will create a default dictionary for our adjacency list and our counter of how many times we have seen each neighbor/child node.  A normal HashMap dictionary would work as well but we would have to create more boiler plate code for checking if an item exists in these before we call them to avoid errors.

        adjacency = collections.defaultdict(list)
        seen = collections.defaultdict(int)

 

For each node and neighbor in the trust edges list, we will make a connection from the node to the neighbor in our adjacency list and increment the number of times that we have seen the neighbor.

        for node, neighbor in trust:
            adjacency[node].append(neighbor)
            seen[neighbor] += 1

 

Then, we will traverse each node in an attempt to find the node that has no neighbors that it trusts, and has been seen in the adjacency list of each other node.

If we find it, we will return it.

        for node in range(1, n+1):
            if not adjacency[node] and seen[node] == n-1:
                return node

 

Otherwise, the node doesn't exist so we will return a negative one.

        return -1