algoadvance

Leetcode 997. Find the Town Judge

Problem Statement

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] = [a, b] representing that the person labeled a trusts the person labeled b.

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

Clarifying Questions

1. Question: What should be returned if there are no people in the town (n = 0)? Answer: Return -1 since it’s not possible to have a town judge without any people.

2. Question: Can there be multiple trust relationships for the same person in the trust list? Answer: Yes, a person can trust multiple other people but in the context of the town judge problem, it does not affect the criterion where a town judge trusts nobody.

3. Question: Is it possible for the trust array to be empty? Answer: Yes, if trust is empty and n is 1, the single individual is by definition the town judge.

Strategy

1. Understand the trust relationships:
   • Use an array to count the number of people each person trusts.
   • Use another array to count how many people trust each person.
2. Determine the town judge:
   • The town judge must trust nobody (should have a trust count of 0).
   • The town judge must be trusted by exactly n-1 people.
3. Iterate over the counts to find the town judge:
   • Check for the conditions in the trust counts array to identify the judge.

Code

public class FindTownJudge {
    public int findJudge(int n, int[][] trust) {
        if (n == 0) return -1;
        if (trust.length == 0 && n == 1) return 1;

        int[] trustCount = new int[n + 1];
        int[] trustedByCount = new int[n + 1];

        for (int[] t : trust) {
            trustCount[t[0]]++;
            trustedByCount[t[1]]++;
        }

        for (int i = 1; i <= n; i++) {
            if (trustCount[i] == 0 && trustedByCount[i] == n - 1) {
                return i;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        FindTownJudge solution = new FindTownJudge();
        int[][] trust = { {1, 2}, {2, 3}, {3, 1} };
        int result = solution.findJudge(3, trust);
        System.out.println(result); // Outputs: -1
    }
}

Time Complexity

• Time Complexity: The solution iterates through the trust array once (O(m)), where m is the number of trust relationships. Then, it iterates through the list of people once (O(n)). Therefore, the overall time complexity is O(m + n).

• Space Complexity: The space complexity is O(n) for the arrays that are used to count the trust relationships.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?