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:
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 <= 10000 <= trust.length <= 104trust[i].length == 2trust are unique.ai != bi1 <= ai, bi <= nThe idea is to calculate the in-degree and out-degree for each person. A person is the town judge if their in-degree is n-1 (trusted by all other n-1 people) and their out-degree is 0 (trusting no one).
This C program uses two arrays to store in-degrees and out-degrees of each person. It then iterates through the trust array to update these values accordingly. Finally, it searches for a person whose in-degree is n-1 and out-degree is 0, identifying them as the judge if they exist.
C++
Java
Python
C#
JavaScript
Time Complexity: O(trust.length), where trust.length is the total number of trust relationships.
Space Complexity: O(n), where n is the number of people in the town.
An alternative approach is to use a single array to calculate the difference between in-degrees and out-degrees. For the judge, this difference should be n-1.
This C implementation uses a single array to track the net trust value of each person. A candidate judge should have a net positive trust equal to n-1.
C++
Java
Python
C#
JavaScript
Time Complexity: O(trust.length)
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| In-Degree and Out-Degree Calculation | Time Complexity: O(trust.length), where trust.length is the total number of trust relationships. |
| Graph Representation Using Single Array | Time Complexity: O(trust.length) |
LeetCode 997. Find The Town Judge (Algorithm Explained) • Nick White • 22,298 views views
Watch 9 more video solutions →Practice Find the Town Judge with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor