Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Solution: Find the Town Judge

Understand how to use graph theory to find the town judge by examining trust relationships. This lesson guides you through calculating indegree and outdegree values to identify the unique person trusted by all yet trusts no one. Learn to implement an efficient algorithm with O(e) time complexity to solve this problem in coding interviews.

We'll cover the following...

Statement

There are n people numbered from 11 to n in a town. There’s a rumor that one of these people is secretly the town judge. A town judge must meet the following conditions:

  1. The judge doesn’t trust anyone.

  2. Everyone else in the town (except the town judge) trusts the judge.

  3. There is exactly one person who fulfills both the above conditions.

You are given an integer n and a two-dimensional array, trust, where each entry trust[i]=[ai,bi]trust[i] = [a_i, b_i] indicates that the person labeled aia_i ...