Find the Town Judge

EASY

Description

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

Approaches

Checkout 3 different approaches to solve Find the Town Judge. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach involves iterating through each person from 1 to n and checking if they meet the criteria of a town judge. For each person, we scan the entire trust list to verify the two conditions: they trust no one, and everyone else trusts them.

Algorithm

Loop through each person i from 1 to n, considering them as a potential judge.
For each candidate i, we need to verify two conditions by scanning the entire trust array:
1. Trusts Nobody: Check if there is any entry [i, x] in the trust array. If one is found, i cannot be the judge.
2. Trusted by Everyone Else: Count the number of people who trust i. This is the number of entries [x, i] in the trust array.
If a candidate i trusts no one AND is trusted by exactly n - 1 people, they are the judge. Return i.
If the loop finishes without finding a judge, it means no one satisfies the conditions. Return -1.

The algorithm considers every person from 1 to n as a potential candidate for the town judge. For each candidate i, we perform two checks by iterating through the trust array:

Check if i trusts anyone: We scan the trust array. If we find an entry [i, x], it means candidate i trusts person x, violating the first rule. Thus, i cannot be the judge, and we move to the next candidate.
Check if i is trusted by everyone else: We count how many people trust candidate i. We iterate through the trust array and increment a counter for every entry [x, i].

If a candidate i trusts no one (passes check 1) and is trusted by exactly n-1 people (passes check 2), we have found the judge. Since the problem guarantees at most one judge, we can immediately return i. If we check all n people and none satisfy both conditions, it means no judge exists, and we return -1.

class Solution {
    public int findJudge(int n, int[][] trust) {
        for (int i = 1; i <= n; i++) {
            int trustedByCount = 0;
            boolean trustsSomeone = false;

            // Check if candidate 'i' trusts anyone
            for (int[] relation : trust) {
                if (relation[0] == i) {
                    trustsSomeone = true;
                    break;
                }
            }

            if (trustsSomeone) {
                continue; // This candidate is disqualified, move to the next
            }

            // Check how many people trust candidate 'i'
            for (int[] relation : trust) {
                if (relation[1] == i) {
                    trustedByCount++;
                }
            }

            // Check if conditions are met
            if (trustedByCount == n - 1) {
                return i; // Found the judge
            }
        }

        return -1; // No judge found
    }
}

Complexity Analysis

Time Complexity: O(N * E), where N is the number of people and E is the number of trust relationships. For each of the N candidates, we iterate through all E relationships.Space Complexity: O(1), as we only use a few variables for counting and flags, not dependent on the input size.

Pros and Cons

Pros:

Simple to understand and implement.
Uses constant extra space.

Cons:

Highly inefficient for larger inputs as it repeatedly scans the trust array, leading to a high time complexity.

Code Solutions

Checking out 3 solutions in different languages for Find the Town Judge. Click on different languages to view the code.

class Solution {
public
  int findJudge(int n, int[][] trust) {
    int[] cnt1 = new int[n + 1];
    int[] cnt2 = new int[n + 1];
    for (var t : trust) {
      int a = t[0], b = t[1];
      ++cnt1[a];
      ++cnt2[b];
    }
    for (int i = 1; i <= n; ++i) {
      if (cnt1[i] == 0 && cnt2[i] == n - 1) {
        return i;
      }
    }
    return -1;
  }
}

Video Solution

Watch the video walkthrough for Find the Town Judge

Data Structures:

ArrayHash TableGraph

Companies:

Turing |Arista Networks |