Problem 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.
Key Insights
- The town judge does not trust anyone, meaning their trust count is zero.
- Everyone else (n-1 people) should trust the town judge, leading to a trust count of (n-1).
- We can use a counting approach to track how many people trust each person.
- If one person has a trust count of (n-1) and no one trusts them, they are the town judge.
Space and Time Complexity
Time Complexity: O(n + t) where n is the number of people and t is the number of trust relationships.
Space Complexity: O(n) for storing the trust counts.
Solution
We will use an array to keep track of the trust counts for each person. We will iterate through the trust relationships to populate this array. Finally, we will check for a candidate who has a trust count of (n-1) and verify that they are trusted by nobody.