Find the Town Judge

📋

Problem

In a small town, everyone trusts exactly one person except the town judge, who trusts nobody but is trusted by everyone else. Can you find out who the judge is?

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: 1. The town judge trusts nobody. 2. Everybody (except for the town judge) trusts the town judge. Given an array trust where trust[i] = [a, b] representing that the person labeled a trusts the person labeled b, return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

1 ≤ n ≤ 10^50 ≤ trust.length ≤ 10^6trust[i].length == 21 ≤ trust[i][0], trust[i][1] ≤ ntrust[i][0] != trust[i][1]

Edge cases: n = 1, trust = [] → 1 (single person is trivially the judge)trust = [] with n > 1 → -1 (no trust relationships means no judge)trust contains cycles → -1 (judge cannot trust anyone)

</>

IDE

def findJudge(n: int, trust: list[list[int]]) -> int:public int findJudge(int n, int[][] trust)int findJudge(int n, vector<vector<int>>& trust)function findJudge(n, trust)

def findJudge(n, trust):
    # Write your solution here
    pass

class Solution {
    public int findJudge(int n, int[][] trust) {
        // Write your solution here
        return -1;
    }
}

#include <vector>
using namespace std;

int findJudge(int n, vector<vector<int>>& trust) {
    // Write your solution here
    return -1;
}

function findJudge(n, trust) {
    // Write your solution here
    return -1;
}

Common Bugs to Avoid

Wrong: -1 for single person with empty trustNot handling the base case where n=1 and trust list is empty.✅ Add condition: if n == 1 and trust is empty, return 1.

Wrong: Judge candidate who trusts someoneFailing to check that the judge trusts nobody (out-degree zero).✅ Ensure candidate's out-degree is zero before returning as judge.

Wrong: Judge candidate not trusted by everyone elseNot verifying that in-degree equals n-1 exactly.✅ Check that candidate's in-degree == n-1 before returning.

Wrong: Any candidate when trust list is empty and n > 1Ignoring that no judge exists if no trust relationships and multiple people.✅ Return -1 if trust list is empty and n > 1.

Wrong: TLE on large inputsUsing nested loops over trust list for each candidate causing O(n*m) complexity.✅ Use arrays to track in-degree and out-degree in O(n + m) time.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly before moving on.

Check your logic for uniqueness and trust conditions carefully to avoid common pitfalls.

Optimize your solution to linear time complexity to handle large inputs efficiently.

t1_01basic

Input{"n":3,"trust":[[1,3],[2,3]]}

Expected3

⏱ Performance - must finish in 2000ms

Person 3 is trusted by persons 1 and 2 and trusts nobody, so 3 is the town judge.

💡 Think about in-degree and out-degree of each person in the trust graph.

💡 The judge has in-degree n-1 and out-degree 0.

💡 Check for a person trusted by everyone else and who trusts no one.

Why it failed: Returned wrong judge or -1 despite person 3 meeting conditions. Fix by verifying candidate's out-degree is zero and in-degree is n-1.

✓ Correctly identified the town judge using trust counts.

t1_02basic

Input{"n":4,"trust":[[1,3],[2,3],[4,3]]}

Expected3

⏱ Performance - must finish in 2000ms

Person 3 is trusted by persons 1, 2, and 4 and trusts nobody, so 3 is the town judge.

💡 Count how many people trust each candidate and if they trust anyone.

💡 Judge must have in-degree n-1 and out-degree 0.

💡 Verify candidate 3 is trusted by all others and trusts no one.

Why it failed: Incorrect output due to not checking all trust relationships or ignoring out-degree zero condition. Fix by ensuring candidate trusts no one.

✓ Correctly found the judge by checking trust counts.

t2_01edge

Input{"n":1,"trust":[]}

Expected1

⏱ Performance - must finish in 2000ms

Single person with no trust relationships is trivially the judge.

💡 Consider the smallest possible town size.

💡 If n=1 and no trust, that person is the judge by definition.

💡 Return n when trust list is empty and n=1.

Why it failed: Returned -1 or other value for single person with empty trust. Fix by returning n when n=1 and trust is empty.

✓ Correctly handled single person edge case.

t2_02edge

Input{"n":2,"trust":[]}

Expected-1

⏱ Performance - must finish in 2000ms

No trust relationships means no judge can be identified for n>1.

💡 If no one trusts anyone and n>1, no judge exists.

💡 Judge must be trusted by everyone else, so trust list cannot be empty.

💡 Return -1 when trust is empty and n>1.

Why it failed: Returned a judge despite no trust relationships. Fix by checking trust list length and returning -1 if empty and n>1.

✓ Correctly returned -1 when no trust relationships exist for multiple people.

t2_03edge

Input{"n":3,"trust":[[1,2],[2,3],[3,1]]}

Expected-1

⏱ Performance - must finish in 2000ms

Trust cycle exists; no one trusts nobody, so no judge.

💡 Check for cycles where everyone trusts someone else.

💡 Judge must trust nobody, so cycles disqualify all.

💡 Return -1 if no candidate has out-degree zero.

Why it failed: Returned a judge despite trust cycle. Fix by verifying candidate's out-degree is zero.

✓ Correctly identified no judge due to trust cycle.

t3_01corner

Input{"n":4,"trust":[[1,3],[2,3],[3,4],[4,3]]}

Expected-1

⏱ Performance - must finish in 2000ms

Person 3 is trusted by 1,2,4 but trusts 4, so no judge.

💡 Check that the candidate trusts no one.

💡 Even if trusted by many, trusting someone disqualifies candidate.

💡 Return -1 if candidate's out-degree > 0.

Why it failed: Returned 3 despite candidate trusting someone. Fix by ensuring candidate's out-degree is zero.

✓ Correctly rejected candidate who trusts others.

t3_02corner

Input{"n":3,"trust":[[1,3],[2,3],[1,2]]}

Expected3

⏱ Performance - must finish in 2000ms

No one is trusted by everyone else; person 3 is not trusted by person 2 only.

💡 Judge must be trusted by all others.

💡 Check that in-degree equals n-1 exactly.

💡 Return -1 if no candidate has in-degree n-1.

Why it failed: Returned 3 despite not being trusted by everyone. Fix by verifying in-degree == n-1.

✓ Correctly identified no judge due to incomplete trust.

t3_03corner

Input{"n":3,"trust":[[1,3],[2,3],[1,2],[2,1]]}

Expected3

⏱ Performance - must finish in 2000ms

Mutual trust between 1 and 2, no unique judge.

💡 Judge must be unique and trusted by all others.

💡 Mutual trust among others disqualifies judge existence.

💡 Return -1 if multiple candidates or no candidate meets criteria.

Why it failed: Returned a judge despite multiple trust cycles. Fix by ensuring uniqueness and trust conditions.

✓ Correctly returned -1 for no unique judge.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000, trust length up to 10^6; O(n + m) solution must complete within 2 seconds.

💡 Use O(n + m) approach with in-degree and out-degree arrays.

💡 Avoid nested loops over trust list for each candidate.

💡 Precompute trust scores and check conditions in one pass.

Why it failed: TLE due to O(n*m) brute force approach. Fix by using O(n + m) in-degree/out-degree arrays.

✓ Efficient O(n + m) solution confirmed by passing performance test.

Practice

1. Consider the following code snippet for the Keys and Rooms problem:

def canVisitAllRooms(rooms):
    n = len(rooms)
    visited = [false] * n
    count = 0
    def dfs(room):
        nonlocal count
        if visited[room]:
            return
        visited[room] = true
        count += 1
        if count == n:
            return
        for key in rooms[room]:
            dfs(key)
    dfs(0)
    return count == n

rooms = [[1], [2], [3], []]
print(canVisitAllRooms(rooms))

What is the value of count after the DFS call completes?

easy

A. 3

B. 0

C. 1

D. 4

Solution

1. Step 1: Trace DFS calls starting from room 0

   Visit room 0 (count=1), then room 1 (count=2), then room 2 (count=3), then room 3 (count=4).

2. Step 2: Confirm all rooms visited

   Since count equals total rooms (4), DFS stops early and returns true.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All rooms reachable, count matches number of rooms [OK]

Hint: Count increments once per unique room visited [OK]

Common Mistakes:

• Off-by-one error counting rooms
• Assuming count stops at 3 instead of 4
• Confusing count with length of visited list

2. You are given a 2D grid representing land (1) and water (0). You need to find the largest connected group of land cells connected only horizontally or vertically. Which algorithmic approach guarantees finding the maximum size of such a connected land area efficiently?

easy

A. Graph traversal using Depth-First Search (DFS) or Breadth-First Search (BFS) to explore connected components

B. Dynamic Programming that stores maximum island size ending at each cell using previous computations

C. Greedy approach that expands from each land cell by always moving to the neighbor with the largest immediate value

D. Sorting all land cells by their coordinates and merging adjacent cells in sorted order

Solution

1. Step 1: Understand the problem as finding connected components in a grid graph

   Each land cell is a node connected to neighbors horizontally or vertically.

2. Step 2: Recognize that DFS or BFS explores all connected nodes in a component, allowing counting of island size

   Greedy or DP approaches do not guarantee exploring all connected cells correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Graph traversal is the standard method for connected components [OK]

Hint: Connected components in grids -> DFS or BFS [OK]

Common Mistakes:

• Thinking DP can solve connected components directly
• Assuming greedy expansion finds max island
• Confusing sorting with connectivity

3. Identify the bug in the following code snippet intended to find the center of a star graph:

medium

A. Line 4: Incorrect initialization of frequency dictionary

B. Line 9: Incorrect condition to check center node frequency

C. Line 11: Returning node inside loop instead of after loop

D. Line 7: Missing frequency update for node v in each edge

Solution

1. Step 1: Inspect frequency updates

   The code updates frequency for u but misses updating for v, so counts are incomplete.

2. Step 2: Consequence of missing update

   Without counting both nodes per edge, the center node frequency will be underestimated, causing incorrect results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Both nodes in each edge must be counted for correct frequency [OK]

Hint: Both nodes in each edge must be counted [OK]

Common Mistakes:

• Counting only one node per edge
• Incorrect frequency condition
• Returning too early in loop

4. What is the time complexity of the optimal algorithm that finds the minimum number of vertices to reach all nodes in a directed acyclic graph with n nodes and e edges?

medium

A. O(n * e) because each node is processed for all edges

B. O(n + e) because each node and edge is processed once

C. O(n^2) because of nested loops over nodes

D. O(e log n) due to priority queue operations in topological sort

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm iterates over all edges once to build the graph and in-degree array, then processes each node and its edges once during the queue processing.

2. Step 2: Combine complexities

   Building graph: O(e), processing nodes and edges in BFS: O(n + e). No nested loops over all nodes and edges.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time in nodes and edges for DAG traversal [OK]

Hint: Topological sort runs in O(n + e) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n*e)
• Confusing with dense graph complexities
• Thinking priority queues are used

5. Suppose the problem is modified so that diagonal neighbors (top-left, top-right, bottom-left, bottom-right) are also considered connected. Which of the following changes to the BFS algorithm correctly adapts to this new requirement without double counting or missing cells?

hard

A. Add diagonal neighbors to the neighbor list and keep the rest of the BFS code unchanged

B. Use DFS instead of BFS because BFS cannot handle diagonal connections

C. Keep neighbor list unchanged but run BFS twice, once for horizontal/vertical and once for diagonals

D. Add diagonal neighbors to the neighbor list and also mark visited cells immediately when enqueuing them

Solution

1. Step 1: Add diagonal neighbors to the neighbor list

   Include all 8 directions: horizontal, vertical, and diagonal neighbors.

2. Step 2: Mark cells as visited when enqueuing

   This prevents adding the same cell multiple times from different neighbors, avoiding double counting.

3. Step 3: Keep BFS traversal logic unchanged otherwise

   Running BFS twice or switching to DFS is unnecessary and inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Mark visited on enqueue avoids duplicates with expanded neighbors [OK]

Hint: Mark visited on enqueue when neighbors increase [OK]

Common Mistakes:

• Not marking visited on enqueue causing duplicates
• Running BFS multiple times unnecessarily
• Thinking BFS can't handle diagonals