Find the Town Judge

-
In a town, there are N people labeled from 1 to N.  There is a rumor that one of these people is secretly the town judge.
If the town judge exists, then:
  1. The town judge trusts nobody.
  2. Everybody (except for the town judge) trusts the town judge.
  3. There is exactly one person that satisfies properties 1 and 2.
You are given trust, an array of pairs trust[i] = [a, b] representing that the person labeled a trusts the person labeled b.
If the town judge exists and can be identified, return the label of the town judge.  Otherwise, return -1.
Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3
Let's understand the problem, we have an array of people where the 0th index person will trust the 1st index person. Any person with maximum trust N - 1 will be town judge and return the label if not then return -1.
In the above input of trust, 1st person is trusting on 3rd and 4th person. Each person has a judge count and it will increase if a person trusts on him and decrease if he trusts on someone by 1 for each person. It is a very straightforward and simple data structure problem. Let's take a look at the code.

public int findJudge(int N, int[][] trust) {
    int[] judgeCount = new int[N + 1];
    for (int[] person : trust) {
        judgeCount[person[0]]--;
        judgeCount[person[1]]++;
    }
    for (int i = 1; i <= N; i++) {
        if (judgeCount[i] == N - 1) {
            return i;
        }
    }
    return -1;
}
Location: Delhi, India

Comments

Post a Comment

Popular posts from this blog

Recursion

-
Image
The process in which a function calls itself and only works where we call the same operation multiple times with different inputs. In every call, we try to make the problem smaller. There must be a base case where the system will stop the recursion and give you a result back. It internally stores the recursion state in the method call stack. If there is no base condition in the recursion method then it will go into an infinite loop and you might face the StackOverflow Exception . There are several types of recursion:- Head Recursion Tail Recursion Tree Recursion Nested Recursion Head Recursion It will call recursively first then at the end do all the computation. private static int factorial( int number) { return (number== 1 )? number : number* factorial (number- 1 ) ; } factorial(5) (5* factorial(5-1)) (5* (4* factorial(4-1)) (5* (4* (3*factorial(3-1))) (5* (4* (3* (2*factorial(2-1)))) (5* (4* (3* (2* (1*1))))) output = 120 Tail Recur...
Read more

Stack

-
Image
The Stack  looks more like a container which holds the element, will insert element from the top and remove from the top only. It follows the Last in First out(LIFO)  or First In Last out (FILO)  approach. Java uses the method stack area to hold the state of the method if some method calls another method inside it.   public class Demo { public static void main(String[] args) { new Demo().firstCall(); System. out .println( "Main" ); } public void firstCall() { secondCall(); System. out .println( "First" ); } private void secondCall() { thirdCall(); System. out .println( "Second" ); } private void thirdCall() { System. out .println( "Third" ); } } This is how it maintains the method call in the method stack area. It will remove from the top every time and complete its method execution and remove next's top from the stack. This process will continue until th...
Read more

Data Structure & Algorithm

-
Image
I am going to start the complete data structure and algorithm blog series to help the developer community understand the basics and help them become more productive in their work environment. As we all are under lockdown until the next update from the government, I have decided to support my friends and colleague to understand the data structure and algorithm. Let's begin by separating the data structure and algorithm in two terms. When you hear about data structure,  what comes first to your mind. I believe most of you thought of storing any form of data in an efficient way. Yes, You are correct 👍. Now, Second and the most important term is an algorithm , It is a set of rules to be followed to solve a problem. To gain more understanding of the data structure and algorithm, let us take an example:- E.g., We are all going to attend the google conference and they have a single registration desk. If we all reach the registration counter together, to register ourselves. Such a ...
Read more