The Celebrity Profile | Stack and Queue

An in-depth exploration of The Celebrity Problem, covering naive frequency-tracking array solutions, the combinatorial proof for maximum celebrity constraints, and the optimal linear-time $O(N)$ two-pointer elimination algorithm.

1. Problem Statement & Definition

Imagine you are at a party with $N$ people, indexed from $0$ to $N-1$. The relationships between the people are given as an $N \times N$ binary matrix, denoted as matrix.

• Matrix Representation: matrix[i][j] == 1 means that person i knows person j. Conversely, matrix[i][j] == 0 means person i does not know person j.
• The Definition of a Celebrity: A celebrity is a special individual at the party who satisfies two strict conditions:
  1. Known by Everyone: Every other person at the party knows the celebrity ($N-1$ people know him/her).
  2. Knows No One: The celebrity does not know a single person at the party ($0$ people are known by him/her).

Your goal is to identify and return the index of the celebrity. If no such person exists at the party, return -1.

Real-Life Analogy

Real-Life Analogy (The Famous VIP in a Room): Think of a room full of people where one person is an ultra-famous celebrity. Everyone in the room recognizes this celebrity (they wave or say hello to them), but the celebrity is so detached or reclusive that they recognize absolutely no one else in the room. Your job is to find this VIP using the fewest possible questions ("Do you know X?").

2. Understanding the Matrix & Diagonal Properties

Before diving into algorithmic solutions, it is vital to understand the structure of the input matrix.

People: 0, 1, 2, 3 (N = 4)

         Person 0   Person 1   Person 2   Person 3
Person 0 [   0          1          1          0   ]
Person 1 [   0          0          0          0   ]
Person 2 [   0          1          0          0   ]
Person 3 [   0          1          1          0   ]

• Diagonal Elements (matrix[i][i]): The entire main diagonal of the matrix contains 0. This is because a person cannot know themselves (matrix[i][i] is always 0).
• Asymmetry: If matrix[0][2] == 1 (Person 0 knows Person 2), it does not imply that matrix[2][0] == 1. In our matrix above, matrix[2][0] == 0, meaning Person 2 does not know Person 0.

3. The Naive Approach: Frequency Tracking Arrays

The Core Idea

To determine if a person is a celebrity, we can count two distinct metrics for every single person:

1. How many people know me? (knowMe count)
2. How many people do I know? (iKnow count)

If a person is a true celebrity, their statistics will match these exact thresholds:

• knowMe[i] == N - 1 (Everyone knows them)
• iKnow[i] == 0 (They know no one)

Naive Algorithm Walkthrough

1. Create two frequency arrays of size $N$, initialized to 0: knowMe and iKnow.
2. Iterate through every cell (i, j) in the $N \times N$ matrix.
3. If matrix[i][j] == 1, it means person i knows person j. Therefore:
   • Increment iKnow[i] (Person i knows someone).
   • Increment knowMe[j] (Person j is known by someone).
4. After populating the arrays, iterate through all persons from 0 to N - 1 and check if any person satisfies knowMe[i] == N - 1 and iKnow[i] == 0.

Java Implementation (Naive Approach)

public class CelebrityProblemNaive {
    public int findCelebrity(int[][] matrix) {
        int n = matrix.length;
        int[] knowMe = new int[n];
        int[] iKnow = new int[n];

        // Step 1: Populate frequency arrays by traversing the matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    iKnow[i]++;
                    knowMe[j]++;
                }
            }
        }

        // Step 2: Evaluate conditions for each person
        for (int i = 0; i < n; i++) {
            if (knowMe[i] == n - 1 && iKnow[i] == 0) {
                return i; // Found the celebrity
            }
        }

        return -1; // No celebrity found
    }
}

Complexity Analysis of Naive Approach

• Time Complexity: $\mathcal{O}(N^2)$ because we must traverse every element in the $N \times N$ matrix, plus an additional $\mathcal{O}(N)$ scan to check the arrays.
• Space Complexity: $\mathcal{O}(2N) \approx \mathcal{O}(N)$ auxiliary space required for the knowMe and iKnow arrays.

4. Why We Need Optimization & Bounding Maximum Celebrities

While the naive approach works, interviewers will ask for an optimization because it consumes extra space ($\mathcal{O}(N)$) and scans every single relationship regardless of logical eliminations.

Mathematical Proof: How Many Celebrities Can Exist?

• Minimum Celebrities: $0$. If everyone knows everyone, or if relationships form cyclical loops where everyone knows someone else, no celebrity can exist.
• Maximum Celebrities: $1$. You can never have two or more celebrities.

Proof by Contradiction: Assume there are two distinct celebrities, X and Y.

• By definition, a celebrity must know no one. Therefore, X cannot know Y, and Y cannot know X.
• Also by definition, everyone must know a celebrity. Therefore, X must know Y (since Y is a celebrity), and Y must know X (since X is a celebrity).
• This creates a direct contradiction: X both knows and does not know Y. Thus, at most one celebrity can exist in any party of $N$ people.

5. The Optimal Approach: Two-Pointer Elimination

The Core Mental Model

Instead of checking every relationship in an $N \times N$ grid, we can maintain two pointers:

• top = 0 (starting at the first person)
• down = N - 1 (starting at the last person)

We systematically eliminate one person at a time by comparing top and down until top meets down.

Elimination Logic Rules

When comparing person top and person down:

1. If top knows down (matrix[top][down] == 1):
   • top knows someone, so top cannot be a celebrity (celebrities know no one). We increment top (top++).
2. If down knows top (matrix[down][top] == 1):
   • down knows someone, so down cannot be a celebrity. We decrement down (down--).
3. If neither knows each other (matrix[top][down] == 0 and matrix[down][top] == 0):
   • Neither can be the celebrity because a celebrity must be known by everyone (including the other person). We can eliminate both (top++ and down--).

6. Step-by-Step Flow Walkthrough

Let's trace the optimal elimination algorithm using our 4-person matrix:

Verification Phase

Because elimination only narrows down a candidate, we are not 100% sure person 1 is a celebrity yet. We must run a final validation scan on candidate 1:

• Check row 1: All elements must be 0 (knows no one).
• Check column 1: All elements except the diagonal (matrix[1][1]) must be 1 (known by everyone).

If the candidate passes both checks, return 1. Otherwise, return -1.

7. Complete Optimized Java Implementation

public class CelebrityProblemOptimized {
    public int findCelebrity(int[][] matrix) {
        int n = matrix.length;
        int top = 0;
        int down = n - 1;

        // Step 1: Eliminate non-celebrities using two pointers
        while (top < down) {
            if (matrix[top][down] == 1) {
                // Top knows down -> Top cannot be celebrity
                top++;
            } else if (matrix[down][top] == 1) {
                // Down knows top -> Down cannot be celebrity
                down--;
            } else {
                // Neither knows each other -> Both cannot be celebrities
                top++;
                down--;
            }
        }

        // If pointers crossed without finding a candidate
        if (top > down) return -1;

        int candidate = top;

        // Step 2: Verify the single remaining candidate
        for (int i = 0; i < n; i++) {
            if (i == candidate) continue; // Skip diagonal

            // Celebrity must NOT know 'i', and 'i' MUST know celebrity
            if (matrix[candidate][i] == 1 || matrix[i][candidate] == 0) {
                return -1;
            }
        }

        return candidate;
    }
}

8. Complexity Analysis

Summary and Key Takeaways

• Celebrity Definition: A celebrity is known by all ($N-1$ people) and knows no one ($0$ people).
• Upper Bound Constraint: There can be at most one celebrity at any party due to logical contradiction in mutual recognition rules.
• Diagonal Rule: Self-recognition (matrix[i][i]) is always 0 and must be skipped during verification checks.
• Two-Pointer Strategy: By utilizing a top and down pointer, we can eliminate impossible candidates in linear time $\mathcal{O}(N)$ without needing auxiliary arrays.
• Verification is Mandatory: Elimination narrows the candidate pool down to a single suspect, but a full row/column scan is strictly required to confirm celebrity status and prevent false positives.