Leetcode – Find the Town Judge Solution in Python

Spread the love

Graph-based problems often offer unique challenges and require a combination of analytical thinking and algorithmic skills. One such problem is the “Find the Town Judge” on Leetcode. This problem poses a graph-like scenario where understanding of the problem’s narrative plays a crucial role in deriving a solution. This article aims to unpack the problem, provide intuitive explanations, and delve into multiple Python solutions.

Table of Contents

  1. Problem Statement
  2. Initial Thoughts and Understanding
  3. Graph-based Intuitive Approach
  4. Using Arrays for Solution
  5. Time and Space Complexity Analysis
  6. Conclusion

1. Problem Statement

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] represents that the person labeled a trusts the person labeled b.

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

Example:

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

2. Initial Thoughts and Understanding

At first glance, the problem presents characteristics of a directed graph where each person is a node, and each trust relationship forms a directed edge.

Considering the constraints:

  1. The town judge trusts nobody, meaning there are no outward edges from the town judge.
  2. Everyone trusts the town judge, meaning there are N-1 inward edges to the town judge.

By keeping these points in mind, we can model the problem as finding a node with N-1 inward edges and 0 outward edges.

3. Graph-based Intuitive Approach

One approach to solve this is by using a graph. We create a directed graph using an adjacency list and then count the inward and outward edges for each person.

Python Implementation:

def findJudge(N, trust):
    # If there's only one person, they are the judge
    if N == 1:
        return 1

    # Create a dictionary to hold the directed edges
    trust_graph = {}
    for a, b in trust:
        trust_graph.setdefault(a, []).append(b)

    # Check if any node has no outward edges
    for i in range(1, N + 1):
        if i not in trust_graph:
            # Now check if this person is trusted by N-1 other people
            count = sum(1 for key in trust_graph if i in trust_graph[key])
            if count == N - 1:
                return i

    return -1

4. Using Arrays for Solution

We can use two arrays to count the inward and outward edges for each person. The town judge will have an inward count of N-1 and an outward count of 0.

Python Implementation:

def findJudge(N, trust):
    # Arrays to count inward and outward edges
    inward = [0] * (N + 1)
    outward = [0] * (N + 1)

    for a, b in trust:
        outward[a] += 1
        inward[b] += 1

    for i in range(1, N + 1):
        if inward[i] == N - 1 and outward[i] == 0:
            return i

    return -1

5. Time and Space Complexity Analysis

  • Graph-based Intuitive Approach:
    • Time Complexity: O(N+T) where T is the length of the trust array. We iterate over the trust array once and then once over the range of people.
    • Space Complexity: O(T) as we store the trust relationships in a graph.
  • Array-based Solution:
    • Time Complexity: O(N+T). The trust array is traversed once, and then the inward and outward arrays are also traversed.
    • Space Complexity: O(N). The size of the inward and outward arrays are constant with respect to the size of the trust array.

6. Conclusion

The “Find the Town Judge” problem on Leetcode is an excellent representation of how real-world scenarios can be modeled using graph theory and data structures. While the problem can seem complex initially due to its narrative form, breaking it down and translating its conditions into data relationships makes it simpler to approach.

This problem serves as a valuable exercise in understanding graph traversal, the properties of directed graphs, and the practical use of arrays for counting relationships. Whether one uses a graph-based or array-based approach, the critical component is understanding the nature of relationships and constraints provided in the problem statement.

Leave a Reply