Gifting the Mayor

Problem

N people in a room, 1 is a mayor.
Every single person has given a gift to the mayor
But the mayor has given no gifts to anyone
The people in the room could have given gifts to other non mayor people in the room as well (though it's optional)
You're given N, the number of people in the room as input
You need to return the mayor (Say 0, for the 0th person or n-1 for the nth person)
You're given a function gift (i, j), which returns true if i has given a gift to j. Returns false otherwise.

Solution

The straight forward solution is to take i=0 and see if he has given a gift to all other. Next take i=1 and see if he has given a gift to everyone. If at any point you have a person who has not given a gift to anyone, return that person i.e. i. But this is an O(n2) algo.

How can we reduce the complexity to O(n)?

Draw a table nxn. If gift(row, col) is true, mark that box as 1, else mark it as 0. if row=col, then mark the cell with x (meaning that's an invalid box or operation). Now how would you traverse the table to find the row which is completely filled with 0s?

 
 int giftProblem(int n) {
  int row = n-1, col = 0;
  while(row >= 0 && col< n) {
   if(row==col) col++;
   else if(gift(row,col)) row--;
   else col++;
  }
  return row;
 }