Find the Influencer or Celebrity

A celebrity/influencer is a person who doesn’t know anybody but is known to or followed by everybody. Given N peoples and a matrix for known or following information then find the celebrity or influencer among the group of N peoples.

Formally speaking, Given a matrix of following between N users (with ids from 0 to N-1):
* following[i][j] == true iff user i is following user j
* thus following[i][j] doesn’t imply following[j][i].
* Let’s also agree that followingMatrix[i][i] == false
*
* Influencer is a user who is:
* – followed by everyone else and
* – not following anyone himself
*
* Find an Influencer by a given matrix of following,
* or return -1 if there is no Influencer in this group.

For example, Lets suppose we have N=5 peoples {A,B,C,D,E} and the following matrix is as follows –

following[0][3] = 1;
following[0][1] = 1;
following[1][3] = 1;
following[1][0] = 1;
following[1][4] = 1;
following[4][3] = 1;
following[2][3] = 1;
following[2][4] = 1;

then clearly 3 is celebrity.

We can build a directed graph and then find the single vertex that has out degree 0 but in degree = N-1.

Computing in-degree and out-degree of a directed graph will take O(n^2) time. Can we do better? Note that, we can easily proof that there should be only one celebrity c with the two following properties –

1. Everybody knows c
2. c doesn't know anybody        

So, we can compute the celebrity in O(n) time by testing each person for the above properties. We can select a person c as a candidate celebrity and then test if c is indeed a celebrity by testing with next person. If the next person doesn’t know (or follow) the current candidate (or influencer) or the candidate knows the next person then the next person may be the celebrity. We can choose such a candidate and then test if all other person knows the candidate c and the candidate c doesn’t know anybody. If any of these properties fail we say there is no such celebrity (or influencer). The overall complexity is O(n). Below is a simple implementation of the above algorithm –

public static int influencer(int[][] following){
	int influencer = 0;
	
	//find the candidate influencer by testing each person i
	//a person i may be a candidate influencer if s/he follows nobody or som
	for(int i = 1; i < following.length; i++){
		if(following[i][influencer] == 0 || following[influencer][i] == 1){
			influencer = i;
		}
	}
	
	//verify that the candidate influencer is indeed an influencer
	for(int i = 0; i < following.length; i++){
		if(i == influencer){
			continue;
		}
		//to be influencer he/she shouldn't follow anybody and there should be nobody else who doesn't follw him/her
		if(following[i][influencer] == 0 || following[influencer][i] == 1){
			return -1;
		}
	}
	
	return influencer;
}