We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Town Judge

Number: 1039

Difficulty: Easy

Paid? No

Companies: Google, Microsoft, Turing, Amazon, Bloomberg, Adobe, Arista Networks

Problem Description

Given n people labeled from 1 to n and an array trust where trust[i] = [a, b] indicates that person a trusts person b, determine if there is a town judge. The town judge trusts nobody and is trusted by everyone else (n-1 people). Return the label of the town judge if they exist, otherwise return -1.

Key Insights

  • Use in-degree and out-degree concepts from graph theory.
  • The town judge (if exists) will have 0 out-degree (trusts nobody) and an in-degree of n-1 (trusted by everyone else).
  • An efficient one-pass accumulation can be employed by maintaining a score for each person computed as in-degree minus out-degree.

Space and Time Complexity

Time Complexity: O(n + m) where m is the number of trust relationships. Space Complexity: O(n) for tracking the net trust scores or degrees for each individual.

Solution

We can solve the problem by keeping track of how many people trust each individual and how many people each individual trusts. For every trust pair [a, b], decrement the trust score for a (since a trusts someone) and increment the trust score for b (since b is trusted). The town judge will then be the person whose trust score equals n-1, implying they are trusted by all other n-1 people and do not trust anyone at all.

Code Solutions

# Python solution for finding the town judge

def findJudge(n, trust):
    # Create a list to track trust scores for people from 1 to n (using index 0 to n, ignoring index 0)
    trust_scores = [0] * (n + 1)
    
    # Process each trust relationship
    for a, b in trust:
        # Decrement score for person a (trusts somebody)
        trust_scores[a] -= 1
        # Increment score for person b (is trusted by somebody)
        trust_scores[b] += 1
    
    # The town judge should have a trust score of n-1
    for i in range(1, n + 1):
        if trust_scores[i] == n - 1:
            return i
    return -1

# Example usage:
#print(findJudge(2, [[1,2]]))
← Back to All Questions