# 22.02.2024 [997. Find the Town Judge]
Find who trusts nobody and everybody trusts him in [trust, trusted] array.
22.02.2024
997. Find the Town Judge easy
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/515
Problem TLDR
Find who trusts nobody and everybody trusts him in [trust, trusted] array.
Intuition
First, potential judge is from set 1..n
excluding all the people who trust someone trust.map { it[0] }
.
Next, check everybody trust him count == n - 1
.
Another approach is to count in-degree and out-degree nodes in graph.
Approach
For the second approach, we didn’t need to count out-degrees, just make in-degrees non-usable.
Let’s try to shorten the code.
Kotlin: use
toSet
,map
,takeIf
,count
,first
Rust:
find
,map_or
.
Complexity
Time complexity:
O(n)Space complexity:
O(n)
Code
fun findJudge(n: Int, trust: Array<IntArray>) =
((1..n).toSet() - trust.map { it[0] }.toSet())
.takeIf { it.size == 1 }?.first()
?.takeIf { j ->
trust.count { it[1] == j } == n - 1
} ?: -1
pub fn find_judge(n: i32, trust: Vec<Vec<i32>>) -> i32 {
let mut deg = vec![0; n as usize + 1];
for e in trust {
deg[e[0] as usize] += n;
deg[e[1] as usize] += 1;
}
(1..deg.len()).find(|&j| deg[j] == n - 1).map_or(-1, |j| j as i32)
}