0% completed
Problem Statement
You are given a town with n
people, labeled from 1
to n
. Some people trust others. You need to find out if there is a "town judge". The town judge is someone who:
- Everyone else trusts.
- The town judge trusts nobody.
Given n
and an array trust
, where trust[i] = [a<sub>i</sub>, b<sub>i</sub>] means person a<sub>i</sub> trusts person b<sub>i</sub>, return the label
of town judge. If there is no town judge, return -1.
Examples
Example 1:
- Input: n = 4, trust = [[1, 2], [3, 2], [4, 2]]
- Expected Output: 2
- Justification: Person 2 is trusted by persons 1, 3, and 4, and person 2 trusts no one. Hence, person 2 is the town judge.
Example 2:
- Input: n = 3, trust = [[1, 3], [2, 3]]
- Expected Output: 3
- Justification: Person 3 is trusted by persons 1 and 2, and person 3 trusts no one. Hence, person 3 is the town judge.
Example 3:
- Input: n = 3, trust = [[1, 3], [2, 1], [3, 1]]
- Expected Output: -1
- Justification: Person 1 is trusted by persons 2 and 3, but person 1 also trusts person 3. Thus, there is no town judge.
Constraints:
- 1 <= n <= 1000
- 0 <= trust.length <= 10<sup>4</sup>
- trust[i].length == 2
- All the pairs of trust are unique.
- a<sub>i</sub> != b<sub>i</sub>
- 1 <= a<sub>i</sub>, b<sub>i</sub> <= n
Solution
To solve this problem, we can use an approach that involves tracking the trust scores of each person. The idea is to count how many people each person trusts and each person trusted by how many people. If a person is trusted by everyone else and trusts no one, their trust score will reflect that. Specifically, the town judge's trust score should be n - 1
, where n
is the number of people in the town.
This approach is efficient because it only requires a single pass through the trust
array to update the trust scores. Afterward, a single pass through the trust scores is sufficient to identify the town judge. This ensures that the solution works in linear time, making it scalable and effective even for larger inputs.
Step-by-step Algorithm
- Initialize an array
trustScores
of sizen + 1
with all elements set to 0. - Iterate through the
trust
array:- For each pair
[a, b]
intrust
, decrementtrustScores[a]
by 1 and incrementtrustScores[b]
by 1. This indicates that persona
trusts someone (hence,trustScores[a]--
) and personb
is trusted by someone (hence,trustScores[b]++
).
- For each pair
- Check the trust scores:
- Iterate through each person
i
from1
ton
. - If
trustScores[i]
is equal ton - 1
, returni
as the town judge. - If no such person is found, return
-1
.
- Iterate through each person
Algorithm Walkthrough
- Input: n = 4, trust = [[1, 2], [3, 2], [4, 2]]
- Initialize: trustScores = [0, 0, 0, 0, 0]
- Processing trust array:
- Pair [1, 2]: trustScores[1]--, trustScores[2]++ → trustScores = [0, -1, 1, 0, 0]
- Pair [3, 2]: trustScores[3]--, trustScores[2]++ → trustScores = [0, -1, 2, -1, 0]
- Pair [4, 2]: trustScores[4]--, trustScores[2]++ → trustScores = [0, -1, 3, -1, -1]
- Check each person:
- Person 1: trustScores[1] = -1
- Person 2: trustScores[2] = 3 (which is equal to
n - 1
) - Person 3: trustScores[3] = -1
- Person 4: trustScores[4] = -1
- Output: 2
Code
Complexity Analysis
- Time Complexity: O(N + E), where N is the number of people and E is the number of trust relationships. The algorithm iterates through the
trust
array once to update the trust scores and then through thetrustScores
array to identify the town judge. - Space Complexity: O(N), where N is the number of people. An additional array
trustScores
of sizeN + 1
is used to keep track of the trust scores for each person.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible