Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Find the Town Judge
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You are given a town with n people, labeled from 1 to n. Some people trust others. You need to find out if there is a "town judge". The town judge is someone who:

  1. Everyone else trusts.
  2. The town judge trusts nobody.

Given n and an array trust, where trust[i] = [a<sub>i</sub>, b<sub>i</sub>] means person a<sub>i</sub> trusts person b<sub>i</sub>, return the label of town judge. If there is no town judge, return -1.

Examples

Example 1:

  • Input: n = 4, trust = [[1, 2], [3, 2], [4, 2]]
  • Expected Output: 2
  • Justification: Person 2 is trusted by persons 1, 3, and 4, and person 2 trusts no one. Hence, person 2 is the town judge.

Example 2:

  • Input: n = 3, trust = [[1, 3], [2, 3]]
  • Expected Output: 3
  • Justification: Person 3 is trusted by persons 1 and 2, and person 3 trusts no one. Hence, person 3 is the town judge.

Example 3:

  • Input: n = 3, trust = [[1, 3], [2, 1], [3, 1]]
  • Expected Output: -1
  • Justification: Person 1 is trusted by persons 2 and 3, but person 1 also trusts person 3. Thus, there is no town judge.

Constraints:

  • 1 <= n <= 1000
  • 0 <= trust.length <= 10<sup>4</sup>
  • trust[i].length == 2
  • All the pairs of trust are unique.
  • a<sub>i</sub> != b<sub>i</sub>
  • 1 <= a<sub>i</sub>, b<sub>i</sub> <= n

Solution

To solve this problem, we can use an approach that involves tracking the trust scores of each person. The idea is to count how many people each person trusts and each person trusted by how many people. If a person is trusted by everyone else and trusts no one, their trust score will reflect that. Specifically, the town judge's trust score should be n - 1, where n is the number of people in the town.

This approach is efficient because it only requires a single pass through the trust array to update the trust scores. Afterward, a single pass through the trust scores is sufficient to identify the town judge. This ensures that the solution works in linear time, making it scalable and effective even for larger inputs.

Step-by-step Algorithm

  • Initialize an array trustScores of size n + 1 with all elements set to 0.
  • Iterate through the trust array:
    • For each pair [a, b] in trust, decrement trustScores[a] by 1 and increment trustScores[b] by 1. This indicates that person a trusts someone (hence, trustScores[a]--) and person b is trusted by someone (hence, trustScores[b]++).
  • Check the trust scores:
    • Iterate through each person i from 1 to n.
    • If trustScores[i] is equal to n - 1, return i as the town judge.
    • If no such person is found, return -1.

Algorithm Walkthrough

  • Input: n = 4, trust = [[1, 2], [3, 2], [4, 2]]
Image
  • Initialize: trustScores = [0, 0, 0, 0, 0]
  • Processing trust array:
    • Pair [1, 2]: trustScores[1]--, trustScores[2]++ → trustScores = [0, -1, 1, 0, 0]
    • Pair [3, 2]: trustScores[3]--, trustScores[2]++ → trustScores = [0, -1, 2, -1, 0]
    • Pair [4, 2]: trustScores[4]--, trustScores[2]++ → trustScores = [0, -1, 3, -1, -1]
  • Check each person:
    • Person 1: trustScores[1] = -1
    • Person 2: trustScores[2] = 3 (which is equal to n - 1)
    • Person 3: trustScores[3] = -1
    • Person 4: trustScores[4] = -1
  • Output: 2

Code

Python3
Python3

. . . .

Complexity Analysis

  • Time Complexity: O(N + E), where N is the number of people and E is the number of trust relationships. The algorithm iterates through the trust array once to update the trust scores and then through the trustScores array to identify the town judge.
  • Space Complexity: O(N), where N is the number of people. An additional array trustScores of size N + 1 is used to keep track of the trust scores for each person.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible