THE TRUE POLITICIAN

In this post we will learn a very basic concept. Before we dive into the concept, let's have a look at a very  interesting problem. The problem says that :

You are given a group of politicians. Among these politicians your task is to identify the true politician.

A true politician has following qualities:

1. Does not trust anybody.
2. Gains trust of all other politician.

You are given a trust T[ ] array where T[i][j] => i trusts j.

Return the true politician if found else return -1

Note : There can be only one true politician.

Example 1 : N = 3    trust[[1,3 ], [2, 3]]

Output : 3

Example 2 : N = 3    trust[[1,3 ], [2, 3], [3, 1]]

Output : -1

Here N is the total number of politicians in the group.

Now reading these kind of problems can make you recall many concepts. But trust me, most of the graph based questions can be solved easily when you draw it on a piece of paper. Consider this example:

N = 4    trust = [

                            [1,4],

                            [2,3],

                            [2,4],

                            [3,4],

                        ]

Let's draw the relations:

                

In the above diagram, we can clearly see that 4  is the true politician. 

How did you find it? 

Exactly, you are thinking in right direction. Here in-out degree of the nodes will come to our rescue. We can clearly see the in-degrees and out-degrees of the nodes. Let X,  be the true politician. Now X do not trust anybody that means that the out-degree of X will be 0. Similarly, it is given that X gains trust of all other politicians, that means the in-degree of X will be N-1.

Now let's write an algorithm.

Algorithm 1 : 

1. Create two arrays of size N + 1 (For 1-based indexing) namely trustCount and outTrustCount.
2. Now we iterate through trust array and maintain in-degree of ith node in trustCount and out-degree in outTrustCount.
3. Finally we will iterate from i = 1 to N +1 and find a node i such that trustCount[i] = N - 1 and outTrustCount[i] = 0. If found we will return i else we will return -1

Damn easy, right? Now let's look at the implementation of above algorithm.

class Solution {
    public int findTruePolitician(int N, int[][] trust) {
        int [] trustCount = new int[N + 1];
        int [] outTrustCount = new int[N + 1];
        for(int[] row : trust){
            outTrustCount[row[0]]++;
            trustCount[row[1]]++;
        }
        for(int i = 1; i <= N; i++)
            if(trustCount[i] == N - 1 && outTrustCount[i] == 0) return i;
        return -1;
    }
}

Time Complexity : O(E + N) where E is number of edges

Space Complexity : O(N)

Can we do better?

Yes, instead of creating 2 arrays we can use just one array. Now let's see another algorithm which have same time and space complexities as Algorithm 1, but a better code in terms of implementation.

Algorithm 2 : 

1. Create an array trustCount  of size N + 1 (again for 1-based indexing).
2. Now we iterate through trust array and maintain in-degree of ith node in trustCount by incrementing trustCount[i] by 1 and out-degree of jth node by decreasing trustCount[j] by 1
3. At last we will iterate trustCount and find for a node with value trustCount[node] = N - 1. If found we return the node else we return -1.

The implementation of above algorithm is as follows:

class Solution {
    public int findTruePolitician(int N, int[][] trust) {       
        int [] trustCount = new int[N + 1];
        for(int[] row : trust){
            trustCount[row[0]]--;
            trustCount[row[1]]++;
        }
        
        for(int i = 1; i <= N; i++)
            if(trustCount[i] == N - 1) return i;
        
        return -1;
    }
}

The above code is short and clean.

Happy Coding 😀