LeetCode 277: Find the Celebrity

Explanation:

To solve this problem, we need to identify a "celebrity" within a group of n people. A celebrity is someone who is known by everyone, but knows no one. The input is given as a square matrix where matrix[i][j] is true if person i knows person j. We need to find the celebrity if one exists, or return -1 otherwise.

We can solve this problem using a two-pointer approach. We start with two pointers, left and right, where left starts at 0 and right starts at n-1. We iterate until left < right. For each pair of left and right, we check if left knows right. If left knows right, then left cannot be the celebrity, so we increment left. If left does not know right, then right cannot be the celebrity, so we decrement right. After completing the iteration, we check if the potential celebrity found at left is known by everyone and knows no one, and if so, we return that person as the celebrity. If there is no celebrity found, we return -1.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of people.

Space Complexity:

The space complexity of this algorithm is O(1) as we are using a constant amount of extra space.

:

class Solution {
    public int findCelebrity(int n) {
        int left = 0, right = n - 1;
        
        while (left < right) {
            if (knows(left, right)) {
                left++;
            } else {
                right--;
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (i != left && (knows(left, i) || !knows(i, left))) {
                return -1;
            }
        }
        
        return left;
    }
}