Find the Town Judge

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
WalmartApple

Problem statement 

1. The judge trust nobody
2. Everybody trusts the judge
3. There is only one judge.

You are given an array/list of pairs, representing that the first value of the pair trusts the second value of the pair. You need to find the town judge. If there is no possible judge return -1.

Note: 
Note that the judge is also numbered similar to the rest of the town members.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’ which denotes the number of test cases. 

The first line of each test case contains two space-separated integers ‘N’ and ‘X’, denoting the number of people in the town and the number of queries regarding who trusts whom.

The next ‘X’ lines of each test contain an array of ‘X’ pairs where each pair denotes who trusts whom in the town.
Output Format: 
For each test case, you need to return a single integer denoting the judge.

Print the output of each test case in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 1000
0 <= X <= 1000
1 <= Y1, Y2 <= N

Where 'Y1' and 'Y2' denotes who trusts whom in the town.

Time limit: 1 sec
Sample Input 1:
2
2 1
1 2
3 2
2 1
3 1
Sample Output 1:
2
1
Explanation of Sample Output 1:
In test case 1, There are only 2 members in the town and person 1 trusts person 2, so person 2 is the judge so return 2.

In test case 2, Both 2 and 3 persons trust the person 1 and so person 1 is judge so return 1.
Sample Input 2:
2
3 2
1 2
3 2
3 3
1 2
3 2
2 1
Sample Output 2:
2
-1
Explanation of Sample Output 2:
In test case 1, There are 3 members in the town and person 1 trusts person 2 and person 3 trusts person 2, so person 2 is the judge so return 2.

In test case 2, There are 3 members in the town and person 1 trusts person 2 and person 3 trusts person 2 but at the same time person 2 trusts person 1, so there is no possible person who can be the judge, so return -1.
Hint

Can you think of storing the edges direction connected to a person?

Approaches (1)
Using Graph Algorithms

In this approach, we will be creating two arrays to count the number of incoming and outgoing edges on a certain person. For any outgoing edges let’s say from A to B, we will surely know that A is not the judge, as A trusts B but a judge doesn't trust anyone.

 

For incoming edges A to B, we increment the counter of count[B], where the count is the array used. When we know there are ‘N’ - 1 incoming connection, we store B, as it is a possible candidate for being the judge, and move forward. If we come through another candidate let’s say C that also has ‘N’ - 1 incoming connection, we know that no possible judge or answer is valid. So return -1.

 

The steps are as follows:

 

  • Create two vectors and initialize their values to 0. These will store the count of each incoming connection and outgoing connections.
  • Start traversing through each node and increase incoming connections for every second value of the given pair and increase outgoing connections for every first value of the pair.
  • Now, check for a node that has incoming connection = ‘N’ - 1 and outgoing connections = 0 at the same time
    • Node found:
      • Return node
    • Not found:
      • Return -1
Time Complexity

O(N), Where ‘N’ is the number of people in the town.

 

Since we are traversing through the nodes constant time, the overall time complexity is O(N).

Space Complexity

O(N), Where ‘N’ is the number of people in the town.

 

Since the space required for the arrays is O(N), so the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Find the Town Judge
Full screen
Console