DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Celebrity Problem

#algorithms #coding #interview #java

Problem Statement

geeksforgeeks.org

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

Top comments (0)