Log inSign up
mediumGeeksforGeeksNot Started

The Celebrity Problem

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on GeeksforGeeks
Lesson

Problem Statement

A celebrity is a person who is known to all but does not know anyone at a party. A party of N people is represented by an N x N binary matrix M where M[i][j] = 1 means person i knows person j, and M[i][j] = 0 means person i does not know person j.

Find the index (0-based) of the celebrity at the party. If no celebrity is present, return -1.

Note: The diagonal elements M[i][i] are 0 because nobody needs to 'know themselves'.

Example 1 · Celebrity Present:

Input: M = [[0, 1, 0], [0, 0, 0], [0, 1, 0]]
Output: 1
Explanation: Person 0 knows 1. Person 2 knows 1. Person 1 knows nobody (row 1 is all 0). Person 1 is known by everyone (column 1 has 1s from everyone else). Celebrity is 1.

Example 2 · No Celebrity:

Input: M = [[0, 1], [1, 0]]
Output: -1
Explanation: Both people know each other, so neither is a celebrity.

Constraints:

  • 1 <= N <= 3000
  • 0 <= M[i][j] <= 1
  • M[i][i] == 0

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the pairwise elimination invariant: a single question knows(A, B) always disqualifies one of the two.
  • Master the stack-based reduction from N candidates to 1 candidate in N - 1 steps.
  • Verify the final survivor in linear time to guard against false positives.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • Push all N people [0, ..., N-1] into a stack.
  • While stack has >= 2 elements, pop A and B.
  • If M[A][B] == 1, A knows B -> A cannot be celebrity, push B back.
  • Else, A does not know B -> B cannot be celebrity, push A back.
  • When 1 candidate remains, verify their entire row is 0 and column is 1 (except diagonal).

Connected Patterns:

Find the Town JudgeTournament EliminationOnline Stock Span

1. In-Degree and Out-Degree Matrix Scan

Intuition

A celebrity has outDegree == 0 (knows nobody) and inDegree == N - 1 (known by all). Count degrees for everyone and check.

Algorithm

  1. Step 1: Initialize inDegree and outDegree arrays of size N.
  2. Step 2: Loop i from 0 to N - 1 and j from 0 to N - 1.
  3. Step 3: If M[i][j] == 1, increment outDegree[i]++ and inDegree[j]++.
  4. Step 4: Find any person k with outDegree[k] == 0 and inDegree[k] == N - 1.
  5. Step 5: Return k if found, else -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 int celebrity(std::vector<std::vector<int>>& M) {
7 int n = M.size();
8 std::vector<int> inDegree(n, 0), outDegree(n, 0);
9 for (int i = 0; i < n; i++) {
10 for (int j = 0; j < n; j++) {
11 if (M[i][j] == 1) {
12 outDegree[i]++;
13 inDegree[j]++;
14 }
15 }
16 }
17 for (int i = 0; i < n; i++) {
18 if (inDegree[i] == n - 1 && outDegree[i] == 0) {
19 return i;
20 }
21 }
22 return -1;
23 }
24};
25
26int main() {
27 Solution solver;
28 std::vector<std::vector<int>> M = {
29 {0, 1, 0},
30 {0, 0, 0},
31 {0, 1, 0}
32 };
33 std::cout << "Celebrity: " << solver.celebrity(M) << std::endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N^2) — Count in-degrees and out-degrees by iterating through all N x N cells of the matrix.
  • Space complexity: O(N) — O(N) arrays for indegree and outdegree counts.

Why Brute Force Doesn't Scale:

For N = 3,000, N2 = 9,000,000 cell reads.

Two Pointers makes at most 9,000 matrix reads (~3N), 1,000x faster.

2. Stack Elimination

Intuition

Push all people onto a stack. Compare top two candidates A and B. Exactly one candidate is eliminated each step. Verify the single remaining candidate.

Algorithm

  1. Step 1: Push all IDs 0, 1, ..., N - 1 onto stack st.
  2. Step 2: While st.size() > 1, pop A = st.pop() and B = st.pop().
  3. Step 3: If M[A][B] == 1 (A knows B), A is not celebrity -> push B. Else (A does not know B), B is not celebrity -> push A.
  4. Step 4: Let candidate = st.top().
  5. Step 5: Verify candidate: check that M[candidate][i] == 0 and M[i][candidate] == 1 for all i != candidate.
  6. Step 6: If verified, return candidate, else return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4
5class Solution {
6public:
7 int celebrity(std::vector<std::vector<int>>& M) {
8 int n = M.size();
9 std::stack<int> st;
10 for (int i = 0; i < n; i++) st.push(i);
11
12 while (st.size() > 1) {
13 int a = st.top(); st.pop();
14 int b = st.top(); st.pop();
15 if (M[a][b] == 1) {
16 st.push(b); // a knows b -> a cannot be celeb
17 } else {
18 st.push(a); // a doesn't know b -> b cannot be celeb
19 }
20 }
21
22 int candidate = st.top();
23 for (int i = 0; i < n; i++) {
24 if (i != candidate) {
25 if (M[candidate][i] == 1 || M[i][candidate] == 0) {
26 return -1;
27 }
28 }
29 }
30 return candidate;
31 }
32};
33
34int main() {
35 Solution solver;
36 std::vector<std::vector<int>> M = {
37 {0, 1, 0},
38 {0, 0, 0},
39 {0, 1, 0}
40 };
41 std::cout << "Celebrity: " << solver.celebrity(M) << std::endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N) — N - 1 pairwise comparisons to reduce stack down to 1 element, followed by 2N verification queries = 3N = O(N).
  • Space complexity: O(N) — O(N) stack to store candidate IDs.

3. Optimal Two-Pointer Elimination

Intuition

Use two pointers i = 0 and j = n - 1. If M[i][j] == 1, i knows j -> i cannot be celebrity (i++). Else j cannot be celebrity (j--). When i == j, verify the candidate.

Algorithm

  1. Step 1: Set i = 0 and j = n - 1.
  2. Step 2: While i < j, if M[i][j] == 1 then i++, else j--.
  3. Step 3: Let candidate = i.
  4. Step 4: Verify candidate by checking row candidate has all 0s and column candidate has all 1s (except diagonal).
  5. Step 5: Return candidate if valid, else -1.

Celebrity Elimination Execution Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
2 eliminated
Visual state
Values and pointers at this exact step
matrix
r0
Why this step matters

2 eliminated.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 int celebrity(std::vector<std::vector<int>>& M) {
7 int n = M.size();
8 int i = 0, j = n - 1;
9 while (i < j) {
10 if (M[i][j] == 1) {
11 i++; // i knows j -> i cannot be celebrity
12 } else {
13 j--; // i does not know j -> j cannot be celebrity
14 }
15 }
16
17 int candidate = i;
18 for (int k = 0; k < n; k++) {
19 if (k != candidate) {
20 if (M[candidate][k] == 1 || M[k][candidate] == 0) {
21 return -1;
22 }
23 }
24 }
25 return candidate;
26 }
27};
28
29int main() {
30 Solution solver;
31 std::vector<std::vector<int>> M = {
32 {0, 1, 0},
33 {0, 0, 0},
34 {0, 1, 0}
35 };
36 std::cout << "Celebrity: " << solver.celebrity(M) << std::endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N) — N - 1 pointer steps to find the candidate + 2N verification steps = 3N = O(N) total comparisons.
  • Space complexity: O(1) — Strictly O(1) auxiliary space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.In-Degree and Out-Degree Matrix ScanO(N^2)O(N)Count degrees for all people by scanning the whole matrix.Scanning the entire N x N matrix.
2.Stack EliminationO(N)O(N)Compare pairs from a stack to eliminate 1 candidate per step.Auxiliary stack allocation.
3.Optimal Two-Pointer EliminationOptimalO(N)O(1)Two pointers at bounds eliminate candidates inward.None (Optimal).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting the verification step and returning the candidate directly (failing cases where no celebrity exists).

Pitfall 2:

Checking diagonal elements M[i][i] during verification.

Pitfall 3:

Using nested loops and achieving O(N2) instead of O(N).

Crucial Edge Cases to Validate:

  • No celebrity exists (everyone knows each other) — Elimination picks a candidate, verification fails, returns -1.
  • No celebrity exists (disconnected components, nobody knows anyone) — Verification fails because in-degree is not N - 1, returns -1.
  • Single person party `N = 1` — Person 0 knows nobody and is known by everyone (trivially), returns 0.
  • Celebrity is person 0 or person N-1 — Handled cleanly at array boundaries.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the fundamental elimination property: M[A][B] == 1 => A is disqualified; M[A][B] == 0 => B is disqualified.
  2. Show how this reduction property enables an O(N) elimination phase.
  3. Always emphasize the verification phase: explain that the survivor is only a *candidate* and must be verified in 2N steps.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is a final verification step necessary after reducing the candidates to 1 person?

2.How many total matrix lookups are performed in the optimal Two-Pointer approach?

Back to DSA Sheet