Find the Celebrity

Problem Statement

Imagine you're at a social gathering with n individuals, each identified by a unique label ranging from 0 to n - 1. Among these attendees, there might be a celebrity. The celebrity is distinct in that every other individual at the event is familiar with them, yet the celebrity doesn't reciprocate this familiarity; they don't know anyone else there. Your task is to determine the identity of the celebrity using the minimum number of questions, which can be phrased as, "Hi, A. Do you know B?" for getting to know whether person A knows person B.

To implement this, you are provided an integer n and a helper function bool knows(a, b) which divulges if person a knows person b. Your objective is to develop the function int findCelebrity(n) that determines and returns the label of the celebrity, if present. If no celebrity exists at the party, the function should return -1.

It's key to remember that the n x n matrix (usually representing known relationships) is not available for direct usage. Access to this relational data between any two individuals is provided solely through the knows function. In this setup, if graph[i][j] == 1, person i knows person j, and if graph[i][j] == 0, it's the opposite.

Examples

Example 1

Input:

graph = [[1,1,0],[0,1,0],[1,1,1]]

Output:

1

Explanation:

There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

Example 2

Input:

graph = [[1,0,1],[1,1,0],[0,1,1]]

Output:

-1

Explanation:

There is no celebrity.

Constraints

• n == graph.length == graph[i].length
• 2 <= n <= 100
• graph[i][j] is 0 or 1.
• graph[i][i] == 1

Approach and Intuition

1. Naive Approach:

   • Iterate over each individual and check against every other attendee to determine if they are known by everyone but do not know anyone else themselves. This approach is direct but not optimal as it requires checking each individual with every other, resulting in an O(n^2) complexity.

2. Optimized Approach (Two Pointer Technique):

   • Initial Elimination:

     • Use a simple elimination logic where two indices (let’s call them i and j) move towards each other. Every time you query knows(i, j), you can make a decision:
       • If i knows j, then i can't be the celebrity. Move i forward.
       • If i does not know j, then j can't be the celebrity. Move j backward.
     • This loop continues until the two pointers meet. The index where they meet is our candidate for celebrity.

   • Verification Stage:

     • Once we have a potential celebrity found in the first pass, a second pass is necessary to confirm that this candidate does not know anyone else (except themselves) and that everyone knows this candidate.
     • Iterate through all attendees again and ensure the candidate meets the criteria of a celebrity. If not, return -1.

   • This optimized method ensures minimization of queries to just around 2n, which is a significant improvement from n^2. In the context of a party with large numbers of attendees, this approach is much more feasible and time-efficient.

Solutions

public class CelebrityFinder extends Relation {
        
    private int totalPeople;
    private Map<Pair<Integer, Integer>, Boolean> relationshipCache = new HashMap<>(); 
        
    @Override
    public boolean knows(int person1, int person2) {
        Pair<Integer, Integer> pair = new Pair<>(person1, person2);
        if (!relationshipCache.containsKey(pair)) {
            relationshipCache.put(pair, super.knows(person1, person2));
        }
        return relationshipCache.get(pair);
    }
        
    public int findCelebrity(int count) {
        totalPeople = count;
        int possibleCelebrity = 0;
        for (int i = 0; i < count; i++) {
            if (knows(possibleCelebrity, i)) {
                possibleCelebrity = i;
            }
        }
        if (checkCelebrity(possibleCelebrity)) {
            return possibleCelebrity;
        }
        return -1;
    }
        
    private boolean checkCelebrity(int candidate) {
        for (int j = 0; j < totalPeople; j++) {
            if (candidate == j) continue; // Skip self checks.
            if (knows(candidate, j) || !knows(j, candidate)) {
                return false;
            }
        }
        return true;
    }
}