Find the Town Judge

Easy

Arista Networks

3 views

Topics:

ArraysGraphs

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:

The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [a_i, b_i] representing that the person labeled a_i trusts the person labeled b_i. If a trust relationship does not exist in trust array, then such a trust relationship does not exist.

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

1 <= n <= 1000
0 <= trust.length <= 10⁴
trust[i].length == 2
All the pairs of trust are unique.
a_i != b_i
1 <= a_i, b_i <= n

Find the Town Judge

Easy

Arista Networks

3 views

Topics:

ArraysGraphs

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:

The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [a_i, b_i] representing that the person labeled a_i trusts the person labeled b_i. If a trust relationship does not exist in trust array, then such a trust relationship does not exist.

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

1 <= n <= 1000
0 <= trust.length <= 10⁴
trust[i].length == 2
All the pairs of trust are unique.
a_i != b_i
1 <= a_i, b_i <= n

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for 'n' (the number of people) and the values within the 'trust' array? Could 'n' be zero?
If no town judge exists, what value should I return?
Can a person trust themselves (e.g., [1, 1] exist in the trust array)? Can the same trust relationship appear multiple times (e.g., [1, 2] appears more than once)?
Is it guaranteed that the 'trust' array will only contain valid pairs of people within the range 1 to n, or could there be invalid entries?
Is the town judge guaranteed to be part of the 'n' people? Or can there be scenarios where the town judge is someone outside of 1 to n?

Brute Force Solution

Approach

The brute force approach to finding the town judge involves checking every person one by one to see if they fit the criteria to be the judge. We assume each person could potentially be the judge and then carefully check all the trust relationships against this assumption.

Here's how the algorithm would work step-by-step:

Consider the first person in town.
Check if everyone else in town trusts this person.
Also check if this person trusts no one else in town.
If both conditions are met, then this person is the judge.
If not, move on to the next person in town.
Repeat the process of checking trust relationships for each person until you find someone who meets both conditions.
If you go through every person and nobody meets the conditions, then there is no judge.

Code Implementation

def find_town_judge_brute_force(number_of_people, trust_relationships):
    for potential_judge in range(1, number_of_people + 1):
        is_judge = True

        # Check if everyone else trusts the potential judge
        for other_person in range(1, number_of_people + 1):
            if other_person != potential_judge:
                trusts_potential_judge = False
                for trust in trust_relationships:
                    if trust[0] == other_person and trust[1] == potential_judge:
                        trusts_potential_judge = True
                        break
                if not trusts_potential_judge:
                    is_judge = False
                    break

        if is_judge:
            # Check if the potential judge trusts no one
            trusts_someone_else = False
            for trust in trust_relationships:
                if trust[0] == potential_judge:
                    trusts_someone_else = True
                    break

            # If no one is trusted, we found the judge
            if not trusts_someone_else:
                return potential_judge

    # No one qualifies to be the judge
    return -1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The brute force algorithm iterates through each person in the town (n people) to check if they are the town judge. For each person, it iterates through the trust array to verify if everyone else trusts them and if they trust no one else. Checking if everyone trusts a potential judge takes O(trust.length), which in the worst case could be proportional to n (number of people). Therefore, for each of the n people, we potentially iterate up to n times to check the trust relationships, resulting in approximately n * n operations. This simplifies to a time complexity of O(n²).

Space Complexity

O(1) – The brute force approach iterates through each person and checks trust relationships. It doesn't require any additional data structures that scale with the input size, N (number of people). Only a few variables are needed to keep track of the current person being evaluated and to count trust relationships. Therefore, the space complexity remains constant, irrespective of the number of people, N, in the town.

Optimal Solution

Approach

The key idea is to track how many people trust each person. We then look for someone who is trusted by everyone else but trusts nobody themselves. This approach avoids directly checking every possible candidate for the town judge.

Here's how the algorithm would work step-by-step:

Imagine each person starts with a 'trust score' of zero.
Go through the list of trust relationships. For each relationship, reduce the 'trust score' of the person doing the trusting (since a judge shouldn't trust anyone) and increase the 'trust score' of the person being trusted.
After processing all the trust relationships, look for a person whose 'trust score' is equal to the total number of people minus one. This means everyone trusts them except themselves.
If you find such a person, check if they trust anyone else. If they don't, they are the town judge.
If no one meets both criteria (being trusted by everyone and trusting no one), there is no town judge.

Code Implementation

def find_judge(number_of_people, trust_relationships):
    trust_scores = [0] * (number_of_people + 1)

    for trust_relation in trust_relationships:
        trusting_person = trust_relation[0]
        trusted_person = trust_relation[1]
        # Reduce score for the truster, since a judge trusts nobody.
        trust_scores[trusting_person] -= 1

        trust_scores[trusted_person] += 1

    # Find the person with a trust score of number_of_people - 1.
    for person_index in range(1, number_of_people + 1):
        if trust_scores[person_index] == number_of_people - 1:
            # Verify if they actually trust anyone.
            is_judge = True
            for trust_relation in trust_relationships:
                if trust_relation[0] == person_index:
                    is_judge = False
                    break
            if is_judge:
                return person_index

    return -1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The primary operation involves iterating through the trust relationships, represented by the 'trust' array. This array can have at most n elements, where n represents the number of people. We create a 'trust score' array of size n to store the trust count for each person. Each trust relationship modifies the trust scores of two people, and then we scan that array to find the judge. Hence, the overall runtime is linearly proportional to the size of the trust array and the number of people.

Space Complexity

O(N) – The algorithm uses a 'trust score' for each person, which can be implemented as an array or hash map of size N, where N is the number of people. This array stores the trust scores for each person. No other significant data structures are used. Therefore, the auxiliary space complexity is directly proportional to the number of people, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty trust array and n = 1	If only one person exists and no one trusts anyone, that person is the town judge.
Empty trust array and n > 1	If no trust relationships exist and more than one person exists, there can be no town judge.
n = 2 and trust only contains one relationship where one person trusts the other	Check if the trusted person trusts anyone else; if they don't, they are the town judge.
No one trusts anyone else	There is no town judge if everyone trusts only themselves, unless n = 1
Multiple potential town judges	The algorithm must verify that only one person meets the criteria for a town judge; if multiple are found, there is no valid judge.
A person trusts themselves	The algorithm should ignore trust relationships where a person trusts themselves, as it's irrelevant to the problem.
Cyclic trust relationships (A trusts B, B trusts A)	The algorithm counts trust relationships, so cycles will not inherently break the logic, but it's necessary to correctly identify the judge candidates.
Integer overflow if n is close to max int and trust relationships are many	Use data types that can accommodate large numbers of trust relationships, considering `n` can be up to 1000.