The person everyone trusts
There are n people, labelled 1 to n. Each pair
[a, b] in trust means person a trusts person b. Exactly one
of them may be the judge, who:
- trusts nobody, and
- is trusted by every one of the other
n − 1people.
Return the judge's label, or −1 if nobody satisfies both conditions.
Examples
| Input | Output | Why |
|---|---|---|
n = 3, trust = [[1,3],[2,3]] | 3 | Both others trust 3, and 3 trusts nobody. |
n = 3, trust = [[1,3],[2,3],[3,1]] | -1 | 3 is trusted by everyone but trusts 1. |
n = 1, trust = [] | 1 | A single person trusts nobody and is trusted by all zero others. |
Constraints
- 1 ≤ n ≤ 1000
- 0 ≤ trust.length ≤ 10⁴
- a ≠ b, and no pair is repeated
Hints
Hint 1
Draw each trust relation as a directed edge a → b. What are the in-degree and out-degree of the judge?
Hint 2
The judge has out-degree 0 and in-degree n − 1. Count both for everyone in one pass over the pairs.
Hint 3
A single score of in-degree minus out-degree is enough: only the judge can reach n − 1.
Where people lose marks
- Checking only the in-degree: someone trusted by all may still trust somebody.
- Returning −1 when n = 1 and there are no pairs. The single person is the judge.
- Indexing an array of size n with labels 1 to n, which overflows on label n.
Dry run on 4,[[1,3],[2,3],[4,3],[1,2]]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5
1 trusts 3: 3 gains a point (now 1), 1 loses one (now -1).
-
Step 2 / 5
2 trusts 3: 3 gains a point (now 2), 2 loses one (now -1).
-
Step 3 / 5
4 trusts 3: 3 gains a point (now 3), 4 loses one (now -1).
-
Step 4 / 5
1 trusts 2: 2 gains a point (now 0), 1 loses one (now -2).
-
Step 5 / 5
Only 3 has score n − 1 = 3: trusted by all three others, trusting nobody. The answer is 3.
How to think about it
As a directed graph with an edge a → b for each pair, the judge is a node with out-degree 0 (trusts nobody) and in-degree n − 1 (trusted by all others). So no search is needed: count degrees.
One counter per person is enough. Add 1 for each edge arriving and subtract 1 for each edge leaving. A person can score n − 1 only if all n − 1 others trust them and they trust nobody, because any outgoing edge costs a point that no further incoming edge can replace: there are only n − 1 others to be trusted by.
Complexity. Time O(n + t) · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def find_judge(n, trust):
score = [0] * (n + 1) # in-degree minus out-degree, labels 1..n
for a, b in trust:
score[a] -= 1 # a trusts someone: cannot be the judge
score[b] += 1
for person in range(1, n + 1):
if score[person] == n - 1:
return person
return -1#include <vector>
int solve(int n, const std::vector<std::vector<int>>& trust) {
std::vector<int> score(n + 1, 0); // in-degree minus out-degree
for (const auto& t : trust) {
--score[t[0]];
++score[t[1]];
}
for (int p = 1; p <= n; ++p)
if (score[p] == n - 1) return p;
return -1;
}class Solution {
public int findJudge(int n, int[][] trust) {
int[] score = new int[n + 1]; // in-degree minus out-degree
for (int[] t : trust) {
score[t[0]]--;
score[t[1]]++;
}
for (int p = 1; p <= n; p++) if (score[p] == n - 1) return p;
return -1;
}
}function findJudge(n, trust) {
const score = new Array(n + 1).fill(0); // in-degree minus out-degree
for (const [a, b] of trust) {
score[a]--;
score[b]++;
}
for (let p = 1; p <= n; p++) if (score[p] === n - 1) return p;
return -1;
}fn solve(n: i64, trust: &[[i64; 2]]) -> i64 {
let mut score = vec![0i64; n as usize + 1]; // in-degree minus out-degree
for t in trust {
score[t[0] as usize] -= 1;
score[t[1] as usize] += 1;
}
(1..=n).find(|&p| score[p as usize] == n - 1).unwrap_or(-1)
}import qualified Data.Map.Strict as M
solve :: Int -> [[Int]] -> Int
solve n trust =
case [p | p <- [1 .. n], M.findWithDefault 0 p score == n - 1] of
(p : _) -> p
[] -> -1
where
-- in-degree minus out-degree
score = M.fromListWith (+) (concat [[(a, -1), (b, 1)] | [a, b] <- trust])
Variants to try
- The celebrity problem: the relation is hidden behind a function knows(a, b), and the goal is to find the celebrity in O(n) calls.
- Return everyone trusted by at least k others who trusts at most one person.
Next problems
Adjacency matrix to adjacency list
Turn an n × n matrix of 0s and 1s into one list of neighbours per node: the conversion behind most graph solutions.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Easy12 minDoes an undirected graph contain a cycle?
Return true if the graph has a cycle: a search that meets a visited node by any edge but the one it came along has found one.
Open the problem →Write a solution and run it against the real test table.
Keep going
Adjacency matrix to adjacency list
Turn an n × n matrix of 0s and 1s into one list of neighbours per node: the conversion behind most graph solutions.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Easy12 minDoes an undirected graph contain a cycle?
Return true if the graph has a cycle: a search that meets a visited node by any edge but the one it came along has found one.
Open the problem → GraphsThe pattern behind it
Grids, networks and dependencies are all graphs. Breadth-first search finds shortest paths, depth-first search and union-find find what is connected, Dijkstra handles weighted edges, and a queue of nodes with no remaining prerequisites gives an order.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.