Find the Town Judge

LeetCode 1039 | Difficulty: Easy

Easy

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.

Example 1:

Input: n = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Constraints:

- `1 <= n <= 1000`

- `0 <= trust.length <= 10^4`

- `trust[i].length == 2`

- All the pairs of `trust` are **unique**.

- `a~i~ != b~i~`

- `1 <= a~i~, b~i~ <= n`

Topics: Array, Hash Table, Graph Theory

---

Approach

Graph Traversal

Model the problem as a graph (nodes + edges). Choose BFS for shortest path or DFS for exploring all paths. For dependency ordering, use topological sort (Kahn's BFS or DFS with finish times).

When to use

Connectivity, shortest path, cycle detection, dependency ordering.

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 437 ms)

Metric	Value
Runtime	437 ms
Memory	49 MB
Date	2022-02-08

Solution

public class Solution {
    public int FindJudge(int n, int[][] trust) {
    
        int[] trusts = new int[n+1];
    int[] isTrusted= new int[n+1];
    
    foreach (var t in trust)
    {
        trusts[t[0]]++;
        isTrusted[t[1]]++;
    }
    
    for (int i = 1; i <= n; i++)
    {
        if(trusts[i]==0 && isTrusted[i] == n-1) return i;
    }
    return -1;
    }
}

📜 1 more C# submission(s)

Submission (2022-02-08) — 453 ms, 48.3 MB

public class Solution {
    public int FindJudge(int n, int[][] trust) {
    
        if(trust.Length == 0 || trust == null) return n==1 ? 1 : -1;
        Dictionary<int, List<int>> d = new Dictionary<int, List<int>>();
    bool[] trusts = new bool[n + 1];

    foreach (var t in trust)
    {
        trusts[t[0]] = true;
        if (d.ContainsKey(t[1]))
            d[t[1]].Add(t[0]);
        else d.Add(t[1], new List<int> {t[0]});
    }

    for (int i = 0; i <= n; i++)
    {
        if (!trusts[i] && d.ContainsKey(i) && d[i].Count == n - 1 && !d[i].Contains(i))
            return i;
    }

    return -1;
    }
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Ask about graph properties: directed/undirected, weighted/unweighted, cycles, connectivity.
• Hash map gives O(1) lookup — think about what to use as key vs value.