Find the Town Judge

▶

Steps

setup

Initialize trust_score array

Create an array trust_score of length n+1 initialized to zero to track net trust for each person.

💡 This array will help us count how many people trust each person and how many people each person trusts.

Line:

trust_score = [0] * (n + 1)

💡 Starting with zero trust scores means no assumptions about trust relationships yet.

traverse

Start processing first trust pair [1,3]

Begin processing the trust relationship where person 1 trusts person 3.

💡 Each trust pair updates trust scores: decrement truster's score, increment trustee's score.

Line:

for a, b in trust:
    trust_score[a] -= 1
    trust_score[b] += 1

💡 We will update trust_score[1] and trust_score[3] based on this trust pair.

fill_cells

Update trust_score for person 1 (decrement)

Person 1 trusts someone, so decrement trust_score[1] by 1 to indicate they trust another.

💡 Decrementing the truster's score tracks that they cannot be the judge if they trust anyone.

Line:

trust_score[a] -= 1

💡 Person 1's trust score changes from 0 to -1.

fill_cells

Update trust_score for person 3 (increment)

Person 3 is trusted by person 1, so increment trust_score[3] by 1.

💡 Incrementing the trustee's score tracks how many people trust them.

Line:

trust_score[b] += 1

💡 Person 3's trust score changes from 0 to 1.

traverse

Start processing second trust pair [2,3]

Begin processing the trust relationship where person 2 trusts person 3.

💡 We will similarly update trust scores for person 2 and person 3.

Line:

for a, b in trust:
    trust_score[a] -= 1
    trust_score[b] += 1

💡 Next trust pair will affect trust_score[2] and trust_score[3].

fill_cells

Update trust_score for person 2 (decrement)

Person 2 trusts someone, so decrement trust_score[2] by 1.

💡 This shows person 2 trusts another, so they cannot be the judge.

Line:

trust_score[a] -= 1

💡 Person 2's trust score changes from 0 to -1.

fill_cells

Update trust_score for person 3 (increment)

Person 3 is trusted by person 2, so increment trust_score[3] by 1 again.

💡 Person 3's trust score increases, showing more people trust them.

Line:

trust_score[b] += 1

💡 Person 3's trust score changes from 1 to 2.

compare

Iterate over person 1 to check trust_score

Check if trust_score[1] equals n-1 (2). It is -1, so person 1 is not the judge.

💡 Only a person trusted by everyone else and trusting no one can be the judge.

Line:

for i in range(1, n + 1):
    if trust_score[i] == n - 1:
        return i

💡 Person 1 fails the judge condition because they trust someone.

compare

Iterate over person 2 to check trust_score

Check if trust_score[2] equals n-1 (2). It is -1, so person 2 is not the judge.

💡 Person 2 also trusts someone, so cannot be the judge.

Line:

for i in range(1, n + 1):
    if trust_score[i] == n - 1:
        return i

💡 Person 2 fails the judge condition because they trust someone.

compare

Iterate over person 3 to check trust_score

Check if trust_score[3] equals n-1 (2). It is 2, so person 3 is identified as the judge.

💡 Person 3 is trusted by everyone else and trusts no one, fulfilling the judge conditions.

Line:

for i in range(1, n + 1):
    if trust_score[i] == n - 1:
        return i

💡 Person 3 is the town judge.

def findJudge(n, trust):
    trust_score = [0] * (n + 1)  # STEP 1: Initialize trust_score array
    for a, b in trust:  # STEP 2-7: Update trust scores for each trust pair
        trust_score[a] -= 1  # STEP 3 & 6: Decrement truster's score
        trust_score[b] += 1  # STEP 4 & 7: Increment trustee's score
    for i in range(1, n + 1):  # STEP 8-10: Check trust scores to find judge
        if trust_score[i] == n - 1:
            return i
    return -1

if __name__ == '__main__':
    print(findJudge(3, [[1,3],[2,3]]))  # Output: 3
    print(findJudge(3, [[1,3],[2,3],[3,1]]))  # Output: -1

📊

Find the Town Judge - Watch the Algorithm Execute, Step by Step

Watching each update to trust scores and the final check reveals the logic behind identifying the judge without needing to read code.

Visiting: none

1

2

3

Visiting: 1

Edge: 1 → 3

1

2

3

Queue / Stack

[1,3]

Visiting: 1

Edge: 1 → 3

1

2

3

Queue / Stack

[1,3]

Visiting: 3

Edge: 1 → 3

1

2

3

Visiting: 2

Edge: 2 → 3

1

2

3

Queue / Stack

[2,3]

Visiting: 2

Edge: 2 → 3

1

2

3

Queue / Stack

[2,3]

Visiting: 3

Edge: 2 → 3

1

2

3

Visiting: 1

1

2

3

Visiting: 2

1

2

3

Visiting: 3

1

2

3

Key Takeaways

✓ The trust_score array efficiently encodes both who trusts whom and who is trusted by whom in a single pass.

This insight is hard to see from code alone because it combines two concepts (trusting and being trusted) into one array.

✓ A person who trusts anyone will have a negative trust score, immediately disqualifying them as the judge.

Visually seeing trust_score decrement clarifies why trusting disqualifies a candidate.

✓ The judge must have a trust score exactly equal to n-1, meaning everyone else trusts them and they trust no one.

The final comparison step shows how the algorithm confirms the judge by this exact condition.

Practice

1. You are given a grid representing water and land cells. The task is to find the water cell that is farthest from any land cell, maximizing the shortest distance to land. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Run a DFS from each water cell to find the nearest land cell and pick the maximum distance found.

B. Perform a multi-source BFS starting simultaneously from all land cells to compute the shortest distance to water cells.

C. Use a greedy approach that picks the water cell farthest from the first land cell found.

D. Apply dynamic programming to store distances from land cells and update iteratively.

Solution

1. Step 1: Understand the problem requires shortest distance from any land cell to water cells.

   DFS from each water cell is inefficient and does not guarantee shortest path globally.

2. Step 2: Multi-source BFS from all land cells simultaneously propagates shortest distances correctly.

   This approach ensures all water cells get the minimum distance to any land cell in O(n^2) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Multi-source BFS finds shortest paths from multiple sources efficiently [OK]

Hint: Multi-source BFS finds shortest distances from all land cells [OK]

Common Mistakes:

• Using DFS for shortest path leads to incorrect distances
• Greedy approach ignores other land cells
• Dynamic programming is not straightforward here

2. Consider the following Union-Find based code snippet to check if a graph is bipartite. Given the graph adjacency list [[1,3],[0,2],[1,3],[0,2]], what is the return value of isBipartite(graph)?

easy

A. true

B. false

C. Raises an exception

D. null (infinite loop)

Solution

1. Step 1: Trace union operations for node 0

   Node 0 neighbors: 1 and 3. Union(1,3) is called. Since 1 and 3 are separate, union succeeds.

2. Step 2: Trace union operations for other nodes

   For node 1 neighbors: 0 and 2. Union(0,2) is called. 0 and 2 are separate, union succeeds. Similarly for node 2 and 3, unions succeed without conflict.

3. Step 3: Check for conflicts

   However, the union-find approach here incorrectly unions neighbors of the same node, which can cause false positives. The code logic is flawed for bipartite checking.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   The code returns false due to a union conflict, indicating the graph is not bipartite [OK]

Hint: Union-Find returns false only on odd cycle detection [OK]

Common Mistakes:

• Confusing union arguments order
• Assuming union returns true on conflict

3. The following code attempts to count the number of islands in a grid using DFS. Identify the line that contains a subtle bug that can cause incorrect island counting or runtime errors.

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols:
            return
        if grid[r][c] == '0':
            return
        # Missing visited marking here
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

medium

A. Line checking if grid[r][c] == '0'

B. Missing line marking grid[r][c] as visited (e.g., grid[r][c] = '0')

C. Line checking if r or c is out of bounds

D. Line incrementing count after DFS call

Solution

1. Step 1: Identify the purpose of marking visited cells

   Marking visited cells prevents revisiting and infinite recursion or double counting.

2. Step 2: Locate missing visited marking

   The code lacks the line that sets grid[r][c] = '0' inside DFS, so visited land cells are never marked.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without marking visited, DFS revisits same cells causing incorrect counts or infinite loops [OK]

Hint: Always mark visited cells to avoid revisiting [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Incorrect boundary checks

4. Suppose the course prerequisites can include self-dependencies (a course requiring itself) and multiple edges between the same courses. Which modification to the Kahn's Algorithm is necessary to correctly detect cycles in this scenario?

hard

A. Ignore self-loops and treat multiple edges as one; no algorithm change needed.

B. Use DFS with coloring instead of Kahn's Algorithm because BFS cannot detect self-loops.

C. Modify in-degree initialization to count self-loops and multiple edges correctly.

D. Add a check to detect self-loops explicitly before running Kahn's Algorithm.

Solution

1. Step 1: Understand impact of self-loops and multiple edges

   Self-loops increase in-degree of a node, and multiple edges increase in-degree counts accordingly.

2. Step 2: Modify in-degree initialization to count all edges accurately

   Counting all edges including self-loops ensures Kahn's Algorithm correctly identifies cycles by never reducing in-degree to zero for cyclic nodes.

3. Step 3: Confirm no other algorithm change needed

   Algorithm logic remains the same; accurate in-degree counts handle these cases.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Proper in-degree counts detect cycles including self-loops [OK]

Hint: Count all edges correctly to detect cycles including self-loops [OK]

Common Mistakes:

• Ignoring self-loops leads to false positives
• Assuming BFS cannot detect self-loops
• Treating multiple edges as single edge incorrectly

5. Suppose the problem is modified so that water can flow uphill by at most 1 unit of height difference (i.e., from a cell to a neighbor if neighbor's height ≥ current height - 1). Which modification to the BFS approach correctly handles this variant?

hard

A. Change the BFS condition to allow neighbor heights >= current height - 1 and keep the rest unchanged.

B. No change needed; original BFS condition already covers uphill flow.

C. Run BFS from each cell individually to check uphill flow possibility.

D. Use a priority queue BFS (Dijkstra) to handle varying height constraints efficiently.

Solution

1. Step 1: Understand uphill flow constraint

   Allowing uphill flow by 1 unit means edges have weights or costs, not uniform.

2. Step 2: BFS is insufficient

   Standard BFS assumes uniform edge cost; to handle varying constraints, Dijkstra's algorithm with a priority queue is needed.

3. Step 3: Modify algorithm

   Use priority queue BFS (Dijkstra) to explore cells with minimal cost respecting height difference constraints.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Uphill flow requires weighted graph traversal -> Dijkstra [OK]

Hint: Uphill flow needs weighted BFS -> Dijkstra [OK]

Common Mistakes:

• Trying to fix with simple BFS condition change
• Running BFS from every cell causes TLE