997. Find the Town Judge
Model: qwen2.5-coder:14b
Topics: Graph
FAANG asked: 1
Acceptance rate: 49.8%
Problem Breakdown
The problem involves identifying a town judge in a town with N people. The town judge is defined by two properties:
- The town judge trusts nobody.
- Everybody (except for the town judge) trusts the town judge.
We are given an array of trust pairs, where each pair [a, b] indicates that person a trusts person b. We need to determine if there exists a town judge and return their label. If no such person exists, we return -1.
Inputs:
N: An integer representing the number of people in the town.trust: A list of trust pairs.
Outputs:
- An integer representing the label of the town judge or
-1if no such person exists.
Implicit Constraints/Edge Cases:
- If
N = 1, there is only one person, who by default could be considered the town judge unless there are trust relationships. - If
trustis empty andN > 1, it’s impossible for a town judge to exist because no one trusts anyone else.
Intuition
A brute-force approach would involve checking each person to see if they meet the criteria of being trusted by everyone else and trusting nobody. This approach would have a time complexity of O(N^2) due to nested loops, which is inefficient given the constraints.
The key insight is to use an array to keep track of trust counts for each person:
- Increment the count for people who are trusted.
- Decrement the count for people who trust others.
- The town judge will be the person with a count equal to
N - 1(trusted by everyone else) and not trusting anyone.
This approach reduces the time complexity to O(N + T), where T is the number of trust relationships, making it more efficient.
Approach
- Initialize an array
trust_countsof sizeN + 1to keep track of trust counts for each person (index represents the person). - Iterate through the
trustlist:- For each pair
[a, b], decrementtrust_counts[a]becauseatrusts someone. - Increment
trust_counts[b]becausebis trusted by someone.
- For each pair
- After processing all trust relationships, iterate through the
trust_countsarray to find a person with a count ofN - 1. - If such a person exists, return their label; otherwise, return
-1.
Complexity Analysis
- Time Complexity: O(N + T), where N is the number of people and T is the number of trust relationships.
- Space Complexity: O(N) for storing the
trust_countsarray.
Solution
def findJudge(N, trust):
if N == 1:
return 1 if not trust else -1
trust_counts = [0] * (N + 1)
for a, b in trust:
trust_counts[a] -= 1
trust_counts[b] += 1
for i in range(1, N + 1):
if trust_counts[i] == N - 1:
return i
return -1
Edge Cases Handled
- Single Person (N = 1): If there’s only one person and no trust relationships, they are the judge. Otherwise, no judge exists.
- No Trust Relationships: If
trustis empty andN > 1, no judge can exist because no one trusts anyone else. - Multiple People Trusting Each Other: The algorithm correctly identifies the town judge even if multiple people trust each other, as long as one person meets the criteria of being trusted by everyone else and trusting nobody.