#997

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find the Town Judge

Find the Town Judge is an easy LeetCode problem that challenges you to identify a town judge from trust relationships using hash tables and array scanning.

array hash table graph

Problem Statement

In a town with n people labeled from 1 to n, there is a rumor that one person is the town judge. The town judge is trusted by everyone, but trusts no one. You are given an array trust where each element trust[i] = [ai, bi] represents that person ai trusts person bi. Your task is to determine if there is a town judge, and if so, return their label. If no judge exists, return -1.

A person can only be the judge if they are trusted by everyone but trust no one else. If the trust array contains any cycle or if there is no single person that fulfills the judge criteria, return -1. The challenge lies in determining the judge by scanning the trust relationships efficiently.

Examples

Example 1

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

Output: 2

Example details omitted.

Example 2

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

Output: 3

Example details omitted.

Example 3

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

Output: -1

Example details omitted.

Constraints

1 <= n <= 1000
0 <= trust.length <= 104
trust[i].length == 2
All the pairs of trust are unique.
ai != bi
1 <= ai, bi <= n

Solution Approach

Array Scanning for Trust Relationships

First, iterate through the trust array and count the trust relationships for each person. Track the number of people who trust each individual, and ensure that no one trusts the potential judge.

Use of Hash Table for Efficient Lookup

Utilize a hash table to store the number of people who trust each individual and the number of people they trust. The potential judge should have n-1 trusts and 0 people they trust.

Edge Case Handling

Ensure that edge cases, like when there are no trust relationships or a person is both trusted and trusting others, are properly handled. These cases will ensure that a valid judge is found or return -1 when necessary.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m), where n is the number of people and m is the number of trust relationships. Space complexity is O(n) due to the hash table used for counting the trust relationships.

What Interviewers Usually Probe

Candidate may demonstrate understanding of array scanning combined with hash table usage.
Pay attention to how efficiently the candidate handles edge cases like cyclic trust or no trust relationships.
The problem is a good test of an interviewee's ability to optimize both time and space complexity.

Common Pitfalls or Variants

Common pitfalls

Ignoring edge cases such as no trust relationships or a cyclic trust relationship.
Failing to track both the number of people who trust an individual and the number of people an individual trusts.
Incorrectly assuming that multiple people can fulfill the judge criteria, missing the single judge requirement.

Follow-up variants

Modify the problem where some people can trust multiple individuals, but the judge still remains trusted by all.
Solve the problem with a more constrained trust array, e.g., only half of the people trust others.
Enhance the problem to consider negative trust, where someone can also actively distrust others.

FAQ

How do I approach solving 'Find the Town Judge' efficiently?

Use array scanning to track trust relationships and a hash table for efficient lookups. Ensure no one trusts the judge and that the judge is trusted by all others.

What is the time complexity of the 'Find the Town Judge' problem?

The time complexity is O(n + m), where n is the number of people and m is the number of trust relationships.

How do I handle edge cases in this problem?

Ensure you account for scenarios where no trust relationships exist, or there is a cycle, and handle these cases by returning -1 when no judge is found.

What is the main pattern to solve 'Find the Town Judge'?

The solution uses a combination of array scanning to count trust relationships and hash table lookups to find the individual who is trusted by everyone but trusts no one.

Can 'Find the Town Judge' be solved with a graph approach?

Yes, the problem can also be seen as a graph problem where nodes represent people and edges represent trust. A valid judge corresponds to a node with no outgoing edges and in-degree of n-1.

terminal

Solution

Solution 1: Counting

We create two arrays $cnt1$ and $cnt2$ of length $n + 1$, representing the number of people each person trusts and the number of people who trust each person, respectively.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        cnt1 = [0] * (n + 1)
        cnt2 = [0] * (n + 1)
        for a, b in trust:
            cnt1[a] += 1
            cnt2[b] += 1
        for i in range(1, n + 1):
            if cnt1[i] == 0 and cnt2[i] == n - 1:
                return i
        return -1

Continue Practicing

#928 minimize malware spread ii #924 minimize malware spread #1311 get watched videos by your friends