LeetCode 277: Find the Celebrity Solution
Master LeetCode problem 277 (Find the Celebrity), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
277. Find the Celebrity
Problem Explanation
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.
:
Solution Code
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;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 277 (Find the Celebrity)?
This page provides optimized solutions for LeetCode problem 277 (Find the Celebrity) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 277 (Find the Celebrity)?
The time complexity for LeetCode 277 (Find the Celebrity) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 277 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 277 in Java, C++, or Python.