LeetCode 997. Find the Town Judge

December 03, 2020

The judge will be a value, $j$ such that the pair $(a,j)$ exists for every unique $a$ and there is no $a=j$ .

Our algorithm could look like:

Do a first pass through the input pairs, building a set, $seen$ , of seen $a$ values. The missing value from $1-N$ is the potential judge. If there is more than one missing value, return -1.
Do a second pass through the input pairs, looking for the judge value at every $b$ value. Once $b=j$ has been found for a given $a$ value, remove that $a$ from the $seen$ set. If the ending $seen$ set is nonempty, return -1, otherwise return the judge value.

The second pass could be faster if we created an edge list map on the first pass. We aren't going to do that for now since it wouldn't be asymptotically faster.

This algorithm is $O($ <number of input pairs> $)$ in both time and space complexity.

from typing import List
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.findJudge(2, [[1,2]]), 2)
        self.assertEqual(self.s.findJudge(3, [[1,3],[2,3]]), 3)
        self.assertEqual(self.s.findJudge(3, [[1,3],[2,3],[3,1]]), -1)
        self.assertEqual(self.s.findJudge(3, [[1,2],[2,3]]), -1)
        self.assertEqual(self.s.findJudge(4, [[1,3],[1,4],[2,3],[2,4],[4,3]]), 3)

    def test_empty(self):
        self.assertEqual(self.s.findJudge(1, []), 1)
        self.assertEqual(self.s.findJudge(2, []), -1)
        #self.assertEqual(self.s.findJudge(

class Solution:

    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        seen = {t[0] for t in trust}
        j = None
        for i in range(1, N+1):
            if i in seen:
                continue
            if j:
                return -1
            j = i
        if not j:
            return -1
        for t in trust:
            if t[0] in seen and t[1] == j:
                seen.remove(t[0])
        return j if not seen else -1

if __name__ == "__main__":
    unittest.main()