Find the Town Judge

Find the Town Judge is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Hashing - Frequency Map / Counting subpattern.

Problem statement

There are n people, identified by the integers from 1 through n. Each inner array in trust has the form [a, b], meaning person a trusts person b.

A town judge is a person who trusts nobody, while every other person trusts the judge. Determine whether such a person exists. If it exists, return that person's label; otherwise, return -1.

Implement findJudge in the Solution class with the given signature. The input may describe no trust relationships, and the requirements must hold for all people exactly as stated.

Example 1:

Input: n = 4, trust = [[1,3],[2,3],[4,3]] Output: 3 Explanation: Person 3 trusts nobody, and each of the other three people trusts person 3, so person 3 is the judge.

Example 2:

Input: n = 3, trust = [[1,2],[2,3]] Output: -1 Explanation: Although person 3 is trusted by person 2, person 1 does not trust person 3, so no one satisfies both judge conditions.

Example 3:

Input: n = 1, trust = [] Output: 1 Explanation: With only one person, that person trusts nobody and there are no other people who need to trust the judge.

Constraints:

- 1 <= n <= 1000 - 0 <= trust.length <= 10^4 - trust[i].length == 2 - 1 <= trust[i][0] <= n - 1 <= trust[i][1] <= n - trust[i][0] != trust[i][1] - All pairs in trust are unique

Topics and companies

Topics: Graph, Array, Counting.

How to practise Find the Town Judge on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n + trust.length) time and O(n) space.

Open Find the Town Judge in the code editor, or read the Find the Town Judge editorial for a worked solution with its approach and complexity analysis.

Where Find the Town Judge sits in the DSA pattern sheet

Problems related to Find the Town Judge

Other problems that use the same Hashing - Frequency Map / Counting and Array/Matrix Manipulation Patterns techniques:

Preparing this workspace.