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

Enter fullscreen mode Exit fullscreen mode

Find the celebrity.

Return:

Celebrity Index

OR

-1

Enter fullscreen mode Exit fullscreen mode

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;
    }
}

Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Approach

Notice an important observation.

Suppose:

A knows B

Enter fullscreen mode Exit fullscreen mode

Then:

A

Cannot be Celebrity

Enter fullscreen mode Exit fullscreen mode

Similarly,

If:

A does NOT know B

Enter fullscreen mode Exit fullscreen mode

Then:

B

Cannot be Celebrity

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Compare:

Does Left Know Right ?

Enter fullscreen mode Exit fullscreen mode

YES

Left Cannot Be Celebrity

Move Left++

Enter fullscreen mode Exit fullscreen mode

NO

Right Cannot Be Celebrity

Move Right--

Enter fullscreen mode Exit fullscreen mode

Eventually,

only one candidate survives.

Now simply verify.

Optimal Approach

Step 1

Keep:

left = 0

right = n-1

Enter fullscreen mode Exit fullscreen mode

Step 2

If:

M[left][right] == 1

Enter fullscreen mode Exit fullscreen mode

Move:

left++

Enter fullscreen mode Exit fullscreen mode

Else:

right--

Enter fullscreen mode Exit fullscreen mode

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;
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

      0 1 2

0 → [0 1 1]

1 → [0 0 1]

2 → [0 0 0]

Enter fullscreen mode Exit fullscreen mode

Step 1

Left = 0

Right = 2

Enter fullscreen mode Exit fullscreen mode

Check:

0 knows 2

YES

Enter fullscreen mode Exit fullscreen mode

Move:

Left = 1

Enter fullscreen mode Exit fullscreen mode

Step 2

Check:

1 knows 2

YES

Enter fullscreen mode Exit fullscreen mode

Move:

Left = 2

Enter fullscreen mode Exit fullscreen mode

Candidate:

2

Enter fullscreen mode Exit fullscreen mode

Verification

Row:

0 0 0

Enter fullscreen mode Exit fullscreen mode

Knows nobody ✓

Column:

1

1

0

Enter fullscreen mode Exit fullscreen mode

Everyone knows 2 ✓

Answer:

2

Enter fullscreen mode Exit fullscreen mode

Why Two Pointers Work?

Every comparison removes exactly one person from consideration.

After:

N-1 comparisons

Enter fullscreen mode Exit fullscreen mode

only one possible celebrity remains.

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

Complexity Analysis

Metric Complexity Time Complexity O(N) Space Complexity O(1)

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Mental Model

Compare Two People

↓

Eliminate One

↓

Repeat

↓

One Candidate Left

↓

Verify

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Find the celebrity”

your brain should immediately think:

Candidate Elimination + Verification