Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

The Celebrity Problem

HARDProblemSolveExternal Links

Description

A party is being organized by some people, and among them there may be a celebrity. A celebrity is a person who is known by everyone else at the party but does not know anyone themselves.

You are given a square matrix mat[][] of size n × n, where mat[i][j] = 1 means person i knows person j, and mat[i][j] = 0 means person i does not know person j. Note that mat[i][i] = 1 for all i (everyone knows themselves).

Your task is to find and return the index (0-based) of the celebrity. If no celebrity exists, return -1.

A valid celebrity must satisfy both conditions:

  • Every other person knows the celebrity: mat[i][celebrity] = 1 for all i ≠ celebrity.
  • The celebrity does not know any other person: mat[celebrity][j] = 0 for all j ≠ celebrity.

Examples

Example 1

Input: mat = [[1, 1, 0], [0, 1, 0], [0, 1, 1]]

Output: 1

Explanation: Person 0 knows person 1 (mat[0][1]=1). Person 2 knows person 1 (mat[2][1]=1). Person 1 does not know person 0 (mat[1][0]=0) and does not know person 2 (mat[1][2]=0). So person 1 is known by everyone and knows nobody else — person 1 is the celebrity.

Example 2

Input: mat = [[1, 1], [1, 1]]

Output: -1

Explanation: Person 0 knows person 1, and person 1 also knows person 0. Since both people know each other, neither satisfies the celebrity condition of 'knows nobody else'. There is no celebrity.

Example 3

Input: mat = [[1]]

Output: 0

Explanation: There is only one person at the party. Since there is nobody else, the condition 'known by everyone' is trivially satisfied and 'knows nobody else' is also trivially satisfied. Person 0 is the celebrity.

Constraints

  • 1 ≤ mat.size() ≤ 1000
  • 0 ≤ mat[i][j] ≤ 1
  • mat[i][i] = 1 for all valid i

Editorial

Brute Force

Intuition

The simplest idea is to check every person one by one and ask: 'Could this person be the celebrity?'

For a person i to be a celebrity, two things must hold:

  1. Everyone else knows i: check column i — all entries except mat[i][i] must be 1.
  2. Person i knows nobody else: check row i — all entries except mat[i][i] must be 0.

We can compute these as the indegree (how many people know i) and outdegree (how many people i knows, excluding themselves). A celebrity has indegree = n-1 and outdegree = 0.

Think of it like checking every person's guest card at a party: for each person, you poll the entire room to see if everyone recognizes them, and you also check whether they recognize anyone else. If both conditions hold, that person is the celebrity.

Step-by-Step Explanation

Let's trace through mat = [[1,1,0],[0,1,0],[0,1,1]] (n=3):

Step 1: Compute indegree and outdegree for each person by scanning the entire matrix.

Step 2: Person 0:

  • Row 0 = [1,1,0]. Outdegree = count of 1's excluding self = 1 (knows person 1).
  • Column 0 = [1,0,0]. Indegree = count of 1's excluding self = 0 (nobody knows person 0).
  • Outdegree ≠ 0 → Person 0 is NOT a celebrity.

Step 3: Person 1:

  • Row 1 = [0,1,0]. Outdegree = 0 (knows nobody else).
  • Column 1 = [1,1,1]. Indegree = 2 (persons 0 and 2 both know person 1).
  • Outdegree = 0 AND Indegree = n-1 = 2 → Person 1 IS a celebrity!

Step 4: Person 2:

  • Row 2 = [0,1,1]. Outdegree = 1 (knows person 1).
  • Column 2 = [0,0,1]. Indegree = 0.
  • Outdegree ≠ 0 → Person 2 is NOT a celebrity.

Result: Person 1 is the celebrity. Return 1.

Brute Force — Scanning Indegree and Outdegree — Watch how we scan each row and column of the matrix to compute indegree and outdegree for every person, then identify the celebrity.

Algorithm

  1. Create two arrays: indegree[n] and outdegree[n], both initialized to 0.
  2. For each pair (i, j) where i ≠ j:
    • If mat[i][j] == 1: increment outdegree[i] and indegree[j].
  3. For each person i from 0 to n-1:
    • If indegree[i] == n-1 and outdegree[i] == 0, return i.
  4. If no such person found, return -1.

Code

class Solution {
public:
    int celebrity(vector<vector<int>>& mat) {
        int n = mat.size();
        vector<int> indegree(n, 0), outdegree(n, 0);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && mat[i][j] == 1) {
                    outdegree[i]++;
                    indegree[j]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (indegree[i] == n - 1 && outdegree[i] == 0) {
                return i;
            }
        }
        return -1;
    }
};
class Solution:
    def celebrity(self, mat: list[list[int]]) -> int:
        n = len(mat)
        indegree = [0] * n
        outdegree = [0] * n

        for i in range(n):
            for j in range(n):
                if i != j and mat[i][j] == 1:
                    outdegree[i] += 1
                    indegree[j] += 1

        for i in range(n):
            if indegree[i] == n - 1 and outdegree[i] == 0:
                return i
        return -1
class Solution {
    public int celebrity(int[][] mat) {
        int n = mat.length;
        int[] indegree = new int[n];
        int[] outdegree = new int[n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && mat[i][j] == 1) {
                    outdegree[i]++;
                    indegree[j]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (indegree[i] == n - 1 && outdegree[i] == 0) {
                return i;
            }
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n²)

We scan every cell in the n×n matrix exactly once to compute indegree and outdegree arrays. This requires n² iterations. The final scan to find the celebrity is O(n). Total: O(n²).

Space Complexity: O(n)

We use two auxiliary arrays of size n (indegree and outdegree).

Why This Approach Is Not Efficient

The brute force scans the entire n×n matrix, performing n² lookups. For n up to 1000, that is up to 1,000,000 operations — which is acceptable but far from optimal.

The deeper problem: we are gathering much more information than needed. To determine the celebrity, we don't need to know the full degree of every person. We only need to identify one candidate and verify them.

The key elimination insight: when we ask 'does person A know person B?', regardless of the answer, we eliminate exactly one person from being the celebrity. If A knows B, then A cannot be the celebrity (celebrities know nobody). If A does not know B, then B cannot be the celebrity (everyone must know the celebrity). This means with just n-1 comparisons, we can narrow down to a single candidate, then verify that candidate with another 2(n-1) checks — giving us O(n) total instead of O(n²).

Better Approach - Stack-Based Elimination

Intuition

Imagine everyone at the party stands in a line. You take the first two people and ask person A if they know person B. One of them gets eliminated: if A knows B, then A leaves (they know someone, so they cannot be the celebrity); if A does not know B, then B leaves (not everyone knows B, so B cannot be the celebrity).

The survivor faces the next person in line, and the elimination continues until only one person remains. That last person is the only possible celebrity candidate — but we are not certain yet, so we verify them against everyone.

A stack is a natural data structure for this: push everyone onto the stack, repeatedly pop two people, eliminate one, push the survivor back, and stop when one remains.

Step-by-Step Explanation

Using mat = [[1,1,0],[0,1,0],[0,1,1]], n=3:

Step 1: Push all people onto the stack. Stack = [0, 1, 2] (top = 2).

Step 2: Pop A=2 and B=1. Does person 2 know person 1? mat[2][1]=1 → YES. Person 2 knows someone, so 2 cannot be the celebrity. Eliminate 2, push back 1. Stack = [0, 1].

Step 3: Pop A=1 and B=0. Does person 1 know person 0? mat[1][0]=0 → NO. Person 0 is not known by person 1, so 0 cannot be the celebrity. Eliminate 0, push back 1. Stack = [1].

Step 4: Only person 1 remains. Candidate = 1.

Step 5: Verify person 1:

  • Does person 1 know anyone? mat[1][0]=0, mat[1][2]=0 → No. ✓
  • Does everyone know person 1? mat[0][1]=1, mat[2][1]=1 → Yes. ✓
  • Person 1 passes both checks!

Result: Return 1.

Stack-Based Celebrity Elimination — Watch how pairs of people are popped from the stack, one eliminated based on the 'knows' relationship, and the survivor pushed back until only one candidate remains.

Algorithm

  1. Push all person indices (0 to n-1) onto a stack.
  2. Elimination phase: While the stack has more than one element:
    a. Pop two people: A (top) and B (next).
    b. If mat[A][B] == 1 (A knows B), A cannot be the celebrity. Push B back.
    c. Else (A does not know B), B cannot be the celebrity. Push A back.
  3. The remaining person on the stack is the candidate c.
  4. Verification phase: For every person i ≠ c:
    • If mat[c][i] == 1 (candidate knows someone), return -1.
    • If mat[i][c] == 0 (someone doesn't know candidate), return -1.
  5. Return c.

Code

class Solution {
public:
    int celebrity(vector<vector<int>>& mat) {
        int n = mat.size();
        stack<int> st;

        for (int i = 0; i < n; i++) {
            st.push(i);
        }

        // Elimination phase
        while (st.size() > 1) {
            int a = st.top(); st.pop();
            int b = st.top(); st.pop();

            if (mat[a][b] == 1) {
                st.push(b); // a knows b → a is not celebrity
            } else {
                st.push(a); // a doesn't know b → b is not celebrity
            }
        }

        int candidate = st.top();

        // Verification phase
        for (int i = 0; i < n; i++) {
            if (i == candidate) continue;
            if (mat[candidate][i] == 1 || mat[i][candidate] == 0) {
                return -1;
            }
        }
        return candidate;
    }
};
class Solution:
    def celebrity(self, mat: list[list[int]]) -> int:
        n = len(mat)
        stack = list(range(n))

        # Elimination phase
        while len(stack) > 1:
            a = stack.pop()
            b = stack.pop()

            if mat[a][b] == 1:
                stack.append(b)  # a knows b → a is not celebrity
            else:
                stack.append(a)  # a doesn't know b → b is not celebrity

        candidate = stack[0]

        # Verification phase
        for i in range(n):
            if i == candidate:
                continue
            if mat[candidate][i] == 1 or mat[i][candidate] == 0:
                return -1
        return candidate
class Solution {
    public int celebrity(int[][] mat) {
        int n = mat.length;
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            stack.push(i);
        }

        // Elimination phase
        while (stack.size() > 1) {
            int a = stack.pop();
            int b = stack.pop();

            if (mat[a][b] == 1) {
                stack.push(b); // a knows b → a not celebrity
            } else {
                stack.push(a); // a doesn't know b → b not celebrity
            }
        }

        int candidate = stack.pop();

        // Verification phase
        for (int i = 0; i < n; i++) {
            if (i == candidate) continue;
            if (mat[candidate][i] == 1 || mat[i][candidate] == 0) {
                return -1;
            }
        }
        return candidate;
    }
}

Complexity Analysis

Time Complexity: O(n)

The elimination phase performs exactly n-1 comparisons (each comparison removes one person, starting with n people and ending with 1). The verification phase checks at most 2(n-1) matrix lookups. Total: (n-1) + 2(n-1) = 3n-3 = O(n).

Space Complexity: O(n)

The stack initially holds all n person indices. As we pop two and push one, the stack shrinks by 1 each round, but the peak size is n.

Why This Approach Is Not Efficient

The stack-based approach achieves O(n) time complexity, which is already optimal since we must check at least n-1 relationships to confirm a celebrity. However, it uses O(n) extra space for the stack.

Can we do better on space? The elimination logic — comparing two candidates and discarding one — does not actually require a stack. We can simulate the same process with just two pointers: one starting at the beginning (person 0) and one at the end (person n-1). At each step, one pointer moves inward, achieving the same elimination in O(1) space.

Optimal Approach - Two Pointers

Intuition

Instead of using a stack to hold all candidates, we use two pointers — one at person 0 and one at person n-1. At each step, we ask if the left person knows the right person:

  • If yes, the left person cannot be a celebrity (they know someone), so we move the left pointer rightward.
  • If no, the right person cannot be a celebrity (not everyone knows them), so we move the right pointer leftward.

Each comparison eliminates exactly one candidate. After n-1 comparisons, the two pointers meet at a single candidate. We then verify that candidate the same way as before.

Think of it like a tournament bracket played from both ends of a line: the survivor of each matchup advances inward, and the last person standing at the center is the final contestant to be verified.

Step-by-Step Explanation

Using mat = [[1,1,0],[0,1,0],[0,1,1]], n=3:

Step 1: Initialize two pointers: i=0 (left), j=2 (right).

Step 2: Check mat[j][i] = mat[2][0] = 0. Person 2 does NOT know person 0. Since not everyone knows person 0, person 0 cannot be the celebrity. Move i rightward: i=1.

Wait — let's re-check the GFG approach: they check mat[j][i]. If mat[j][i]==1, then j knows i, so j can't be celebrity → j--. Else i can't be celebrity → i++.

Let me re-trace:

Step 2: i=0, j=2. Check mat[j][i] = mat[2][0] = 0. Person 2 does NOT know person 0. If the right person doesn't know the left person, then the left person can't be the celebrity (not known by everyone). So i++. Now i=1.

Step 3: i=1, j=2. Check mat[j][i] = mat[2][1] = 1. Person 2 DOES know person 1. The right person knows the left candidate, so the right person might not be the celebrity. j--. Now j=1.

Step 4: i=1, j=1. Pointers meet! Candidate = 1.

Step 5: Verify candidate 1:

  • Does person 1 know person 0? mat[1][0]=0 ✓
  • Does person 0 know person 1? mat[0][1]=1 ✓
  • Does person 1 know person 2? mat[1][2]=0 ✓
  • Does person 2 know person 1? mat[2][1]=1 ✓
  • All checks pass!

Result: Return 1.

Two Pointers — Celebrity Elimination — Watch how two pointers converge from opposite ends, eliminating one candidate per comparison until a single candidate remains, then verifying that candidate.

Algorithm

  1. Initialize two pointers: i = 0 (left), j = n - 1 (right).
  2. Elimination phase: While i < j:
    • If mat[j][i] == 1 (person j knows person i), then j cannot be a celebrity. Decrement j.
    • Else (person j does not know person i), then i cannot be a celebrity. Increment i.
  3. When i == j, set candidate = i.
  4. Verification phase: For every person k from 0 to n-1 where k ≠ candidate:
    • If mat[candidate][k] == 1, return -1 (candidate knows someone).
    • If mat[k][candidate] == 0, return -1 (someone doesn't know candidate).
  5. Return candidate.

Code

class Solution {
public:
    int celebrity(vector<vector<int>>& mat) {
        int n = mat.size();
        int i = 0, j = n - 1;

        // Elimination phase
        while (i < j) {
            if (mat[j][i] == 1) {
                // j knows i → j is not celebrity
                j--;
            } else {
                // j doesn't know i → i is not celebrity
                i++;
            }
        }

        int candidate = i;

        // Verification phase
        for (int k = 0; k < n; k++) {
            if (k == candidate) continue;
            if (mat[candidate][k] == 1 || mat[k][candidate] == 0) {
                return -1;
            }
        }
        return candidate;
    }
};
class Solution:
    def celebrity(self, mat: list[list[int]]) -> int:
        n = len(mat)
        i, j = 0, n - 1

        # Elimination phase
        while i < j:
            if mat[j][i] == 1:
                # j knows i → j is not celebrity
                j -= 1
            else:
                # j doesn't know i → i is not celebrity
                i += 1

        candidate = i

        # Verification phase
        for k in range(n):
            if k == candidate:
                continue
            if mat[candidate][k] == 1 or mat[k][candidate] == 0:
                return -1
        return candidate
class Solution {
    public int celebrity(int[][] mat) {
        int n = mat.length;
        int i = 0, j = n - 1;

        // Elimination phase
        while (i < j) {
            if (mat[j][i] == 1) {
                // j knows i → j is not celebrity
                j--;
            } else {
                // j doesn't know i → i is not celebrity
                i++;
            }
        }

        int candidate = i;

        // Verification phase
        for (int k = 0; k < n; k++) {
            if (k == candidate) continue;
            if (mat[candidate][k] == 1 || mat[k][candidate] == 0) {
                return -1;
            }
        }
        return candidate;
    }
}

Complexity Analysis

Time Complexity: O(n)

The elimination phase runs while i < j. Each iteration either increments i or decrements j, and since i starts at 0 and j starts at n-1, the loop runs at most n-1 times. The verification phase iterates through n-1 people with two matrix lookups each, giving 2(n-1) lookups. Total: (n-1) + 2(n-1) = 3(n-1) = O(n).

Space Complexity: O(1)

We only use two integer pointer variables (i and j) and one integer for the candidate. No additional data structures are needed, regardless of input size.