Practice › Stack & Queue
The Celebrity Problem
Medium · Stack & Queue · Asked at Amazon, Microsoft, Google, Flipkart, Zoho
M[i][j] = 1 means person i knows person j. A celebrity is known by everyone else but knows nobody. Print the celebrity's index (0-based), or -1 if there is none.
Input
First line: n. Next n lines: n values (0 or 1). M[i][i] = 0.
Output
The celebrity index, or -1.
Constraints
- 1 ≤ n ≤ 1000
Eliminate candidates in pairs: if a knows b, a is not a celebrity; otherwise b is not. One candidate remains — verify it in O(n).
Example 1
Input
3 0 1 0 0 0 0 0 1 0
Output
1
Example 2
Input
2 0 1 1 0
Output
-1
Hints
- One question "does a know b?" always rules somebody out: if yes, a is not a celebrity; if no, b is not.
- After n − 1 questions one candidate is left. Check it: it must know nobody and be known by everyone.
Approach
Keep a candidate c = 0. For i = 1..n−1, if M[c][i] == 1 then c knows someone, so c = i; otherwise i is not known by c and cannot be the celebrity. Nobody else can be the celebrity, but c still might not be one — verify that M[c][i] = 0 and M[i][c] = 1 for all i ≠ c. (The same elimination works with a stack.)
Complexity: O(n) questions after reading the O(n²) matrix · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<int>> M(n, vector<int>(n));
for (auto &row : M)
for (auto &x : row) cin >> x;
int c = 0;
for (int i = 1; i < n; i++)
if (M[c][i]) c = i;
for (int i = 0; i < n; i++) {
if (i != c && (M[c][i] || !M[i][c])) {
cout << -1 << "\n";
return 0;
}
}
cout << c << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
M = [data[1 + i * n : 1 + (i + 1) * n] for i in range(n)]
c = 0
for i in range(1, n):
if M[c][i]:
c = i
ok = all(i == c or (not M[c][i] and M[i][c]) for i in range(n))
print(c if ok else -1)Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
int[][] M = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
in.nextToken();
M[i][j] = (int) in.nval;
}
int c = 0;
for (int i = 1; i < n; i++)
if (M[c][i] == 1) c = i;
for (int i = 0; i < n; i++) {
if (i != c && (M[c][i] == 1 || M[i][c] == 0)) {
System.out.println(-1);
return;
}
}
System.out.println(c);
}
}