Leetcode 997. Find the Town Judge

Problem

Leetcode 997 - Find the Town Judge

Example:

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

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

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

Approach

We can create two maps:

• candidates: key = trusted person, value = trusted by
• trustMap: key = person x, value = people that x trusts

Since we a judge must be trusted by everyone, we can check a key value that has length of $n-1$, and if that key doesn’t exist in trustMap (since a judge must not trust anyone), we can return that key value as a result

Here is the Python code for the solution:

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        candidates = defaultdict(set)
        trustMap = defaultdict(set)

        for a, b in trust:
            trustMap[a].add(b)
            candidates[b].add(a)
        
        for i in range(1, n+1):
            if len(candidates[i]) == n-1 and i not in trustMap:
                return i
        
        return -1   

Time Complexity and Space Complexity

Time Complexity: $O(V+E)$

Space Complexity: $O(V)$