Scale Engineer

Find the Town Judge

Easy
#0951Time: 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: O(1), as we only use a few variables for counting and flags, not dependent on the input size.2 companies
Data structures
ArrayHash TableGraph
Companies
TuringArista Networks

Prompt

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:

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

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi. 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 <= 104
  • trust[i].length == 2
  • All the pairs of trust are unique.
  • ai != bi
  • 1 <= ai, bi <= n

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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:

  1. 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.
  2. 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

Time

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

O(1), as we only use a few variables for counting and flags, not dependent on the input size.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem