Solving acquaintanceship task in linear time

Question

Given set of n people, person A may or may not know person B (also, A knows B doesn't imply that B knows A). All acquaintanceships defined by nxn matrix of booleans.
Let's define celebrity as person, who are known by everybody, but who knows nobody.

Task is to suggest an algorithm, which takes O(n) time and O(1) additional space to find celebrity in the set or to state that set contains none of them.

First of all, I'm under impression, that guys who wrote this had intention to mess a bit with heads of those who will put hands on that problem.

What I think, linear time here means that we are allowed to take time linear compared to the input size, which actually is n*n.
Then proposing quadratic time algorithm seems like trivial task. From other hand, if we suppose that I'm mistaken with my previous statement, I don't believe It's possible to find much in the unsorted matrix with side k with time O(k)...

I will just leave a draft of the quadratic time algorithm here:

for x in range(0,side-1):
    knowingAmount = sumAlongColumn(x)
    if knowingAmount == side:
        celebritySuspectKnows = sumAlongRow(x)
        if celebritySuspectKnows == 1:
            return x
return -1

So, I would appreciate if you guys helped me out here. Am I interpreting this caveat with time complexity requirements right, or more efficient algorithm exists here?

Answer 1

For each person:

• If we have no potential celebrity, let this person be the potential celebrity.

• If neither of the potential celebrity nor this person knows each other, or they both know each other, reset the potential celebrity.

• If the potential celebrity knows this person, but not the other way around, let this person become the new potential celebrity.

---

Or, simplified:

Let the first person be the potential celebrity.

For each person: (from the second)

• If the potential celebrity knows this person, let this person become the new potential celebrity.

---

Once done, if we have a potential celebrity, go through again and check if this person knows no-one else and everyone knows them to make sure they're actually the celebrity.

Complexity: O(n) time, O(1) space.

The keys to proving correctness are:

• We can't move on from a person if that person is the celebrity, because the only criteria to move on is knowing someone else, which is not possible for the celebrity.

• We'll always switch over to the celebrity if one exists, given that we go through all people and always switch over if a person knows this person, which is true for all other people with respect to the celebrity.

But, if there is no celebrity, we'll still have a (non-celebrity) candidate at the end (given that we fairly easily nominate someone as a potential celebrity), so we need to make sure the candidate is the celebrity.

Answer 2

We can solve problem using process of elimination.

One of person can be eliminated based on value of Knows[i][j], where i & j are celebrities.

1. A dosen't know B than, then we can surely eliminate B, as we know every one knows celebrity.
2. A knows B, Then we eliminate A as celebrity knows no one.

Now we can formulate algorithm as

     Push All Celeb on Stack

    while stack is not empty{
     Pop Two Celeb i & j

     if(knows[i][j]) //i knows j
       push j //eliminate i

     else
       push i // i dosen't know j, so j is not celebrity.

    }
    C=(last element on stack)

   /* Now one person remains but we can't gurantee he is celebrity because we might have popped person who doesn’t know or some person he knows from the stack before we reach that celebrity */


   for( all celebrity except C){
        if(!knows[i][C]) return -1;
        if(knows[C][i]) return -1;
   }
   return C;