Celebrity Problem

Problem Statement

A celebrity is a person who:

• Knows no one.
• Is known by everyone else.

Given an N × N matrix:

M[i][j] = 1

→ i knows j

Find the celebrity.

Return:

Celebrity Index

OR

-1

if no celebrity exists.

Brute Force Intuition

In an interview, you can explain it like this:

Check every person individually. Verify whether they know nobody and everybody else knows them.

This requires checking an entire row and column for every person.

Complexity

• Time Complexity: O(N²)
• Space Complexity: O(1)

Brute Force Code

class Solution {

    public int celebrity(int[][] M, int n) {

        for (int i = 0; i < n; i++) {

            boolean celebrity = true;

            for (int j = 0; j < n; j++) {

                if (i == j)
                    continue;

                if (M[i][j] == 1 ||
                    M[j][i] == 0) {

                    celebrity = false;
                    break;
                }
            }

            if (celebrity)
                return i;
        }

        return -1;
    }
}

Moving Towards the Optimal Approach

Notice an important observation.

Suppose:

A knows B

Then:

A

Cannot be Celebrity

Similarly,

If:

A does NOT know B

Then:

B

Cannot be Celebrity

So with one comparison,

we eliminate one candidate.

Pattern Recognition

Whenever you see:

• Eliminate Candidates
• Pairwise Comparison
• Find One Possible Answer

Think:

Two Pointers / Elimination

Key Observation

Start with:

Person 0

Person N-1

Compare:

Does Left Know Right ?

YES

Left Cannot Be Celebrity

Move Left++

NO

Right Cannot Be Celebrity

Move Right--

Eventually,

only one candidate survives.

Now simply verify.

Optimal Approach

Step 1

Keep:

left = 0

right = n-1

Step 2

If:

M[left][right] == 1

Move:

left++

Else:

right--

Step 3

One candidate remains.

Verify:

• Entire Row
• Entire Column

Optimal Java Solution

class Solution {

    public int celebrity(int[][] M, int n) {

        int left = 0;
        int right = n - 1;

        while (left < right) {

            if (M[left][right] == 1) {

                left++;

            } else {

                right--;
            }
        }

        int candidate = left;

        for (int i = 0; i < n; i++) {

            if (i == candidate)
                continue;

            if (M[candidate][i] == 1 ||
                M[i][candidate] == 0) {

                return -1;
            }
        }

        return candidate;
    }
}

Dry Run

Input

      0 1 2

0 → [0 1 1]

1 → [0 0 1]

2 → [0 0 0]

Step 1

Left = 0

Right = 2

Check:

0 knows 2

YES

Move:

Left = 1

Step 2

Check:

1 knows 2

YES

Move:

Left = 2

Candidate:

2

Verification

Row:

0 0 0

Knows nobody ✓

Column:

1

1

0

Everyone knows 2 ✓

Answer:

2

Why Two Pointers Work?

Every comparison removes exactly one person from consideration.

After:

N-1 comparisons

only one possible celebrity remains.

The final verification confirms whether that candidate satisfies the celebrity conditions.

Complexity Analysis

Interview One-Liner

Eliminate one candidate in every comparison using two pointers, then verify the remaining candidate by checking its row and column.

Pattern Learned

Pairwise Elimination

↓

One Candidate Left

↓

Verify Candidate

Similar Problems

• Celebrity Problem
• Find the Judge (LeetCode)
• Gas Station
• Majority Element
• Boyer-Moore Voting Algorithm

Memory Trick

Think:

A Knows B ?

↓

Yes

↓

A Cannot Be Celebrity

-------------------

No

↓

B Cannot Be Celebrity

Mental Model

Compare Two People

↓

Eliminate One

↓

Repeat

↓

One Candidate Left

↓

Verify

Whenever you hear:

"Find the celebrity"

your brain should immediately think:

Candidate Elimination + Verification