38-Celebrity-Problem.md

Celebrity Problem

Problem Link

Practice Problem

---

Pattern

• Stack
• Two Pointer

---

Approach

Eliminate non-celebrities in pairs, then verify the remaining candidate against all people.

---

Time Complexity

O(n)

Space Complexity

O(1)

---

Java Solution

class Solution {
    private boolean knows(int a, int b) {
        return true;
    }

    public int findCelebrity(int n) {
        int candidate = 0;
        for (int i = 1; i < n; i++) {
            if (knows(candidate, i)) candidate = i;
        }
        for (int i = 0; i < n; i++) {
            if (i == candidate) continue;
            if (knows(candidate, i) || !knows(i, candidate)) return -1;
        }
        return candidate;
    }
}