Find the Town Judge - Video Solutions

Problem Overview: You have n people in a town labeled from 1 to n. Some people trust others, represented as pairs [a, b]. The town judge trusts nobody but is trusted by everyone else. Your task is to identify that person or return -1 if such a person does not exist.

Approach 1: In-Degree and Out-Degree Calculation (O(n + m) time, O(n) space)

This problem maps naturally to a graph interpretation where each person is a node and each trust pair is a directed edge from a to b. The judge must have out-degree = 0 (trusts nobody) and in-degree = n - 1 (trusted by everyone else). Iterate through the trust list and update two arrays: one tracking how many people each person trusts, and another tracking how many trust them. After processing all edges, scan people from 1 to n and return the person whose in-degree is n - 1 and out-degree is 0. The algorithm processes each trust pair once, giving O(n + m) time and O(n) space.

Approach 2: Graph Representation Using Single Array (O(n + m) time, O(n) space)

You can compress the in-degree and out-degree idea into one array. Maintain a score array where trusting someone decreases your score and being trusted increases it. For each pair [a, b], decrement score[a] and increment score[b]. After processing all pairs, the judge must end up with score n - 1 because they receive n - 1 trusts and give none. This approach keeps the same linear time complexity while reducing bookkeeping to a single array. The trust relationships are still treated as edges in a conceptual graph structure, but the representation is simplified.

Recommended for interviews: The single-array scoring approach is usually preferred. It shows you recognized the key property of the judge and optimized the graph representation. Explaining the in-degree/out-degree version first demonstrates solid graph reasoning, while the compressed array solution shows practical optimization and clean implementation.