#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/graph-fundamentals/town-judge-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/graph-fundamentals/town-judge-implementation

Repovive

Town Judge - Implementation - Graph Fundamentals | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Town Judge - Implementation

Writing the Code

Here is the solution:

function findJudge(n, trust):
    countOut = array of size n + 1, all 0
    countIn = array of size n + 1, all 0

    for (u, v) in trust:
        countOut[u] = countOut[u] + 1
        countIn[v] = countIn[v] + 1

    for i from 1 to n:
        if countOut[i] == 0 and countIn[i] == n - 1:
            return i

    return -1

This runs in $O(n)$ time and uses $O(n)$ space.