Coding

Celebrity Problem

Asked at

Flexport

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

A celebrity is a person who is known by everyone else at the party but does not know anyone in return. Given a square matrix M of size N x N where M[i][j] is 1 if person i knows person j, and 0 otherwise, determine if there is a celebrity at the party. Return the index of the celebrity or -1 if no such person exists.

Note that M[i][i] is always 0.

Input: M = [ [0, 1, 1, 0], [0, 0, 0, 0], [1, 1, 0, 0], [0, 1, 1, 0] ] Output: 1 Explanation: Person 1 does not know anyone and is known by persons 0, 2, and 3. Therefore, person 1 is the celebrity.

Input: M = [ [0, 1], [1, 0] ] Output: -1 Explanation: Both persons know each other, so there is no celebrity.

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

1 <= N <= 3000
0 <= M[][] <= 1

cpp

class Solution
{
public:
    int celebrity(vector<vector<int>> &M){
        
    }
};

java

class Solution {
    public int celebrity(int[][] M) {
      
    }
}

python

class Solution:
    def celebrity(self, M):

javascript

class Solution {
    celebrity(M) {
     
    }
}

csharp

public class Solution
{
    public int celebrity(List<List<int>> M){
        
    }
}

func celebrity(M [][]int) int {

}

Stuck? Show a way to structure it+

01Eliminate one of two people at each comparison to obtain a single candidate.
02If candidate knows i, candidate is replaced by i; otherwise i is eliminated.
03Verify that the candidate knows nobody and everyone else knows the candidate.
04Return no result when the final verification fails.

Reference answer

Start with candidate zero. For each person i from one onward, if candidate knows i, the candidate cannot be a celebrity, so set candidate to i. Otherwise i cannot be a celebrity because the current candidate does not know them. This eliminates one person per comparison and leaves the only possible candidate. Then verify the candidate against every other person: M[candidate][i] must be zero and M[i][candidate] must be one. If any check fails, return -1; otherwise return the candidate. Elimination alone is not sufficient because the matrix may contain no celebrity. Time is O(n) and extra space is O(1). A stack-based pairwise elimination expresses the same proof but uses extra space.

Then expect these follow-ups

Why does each comparison safely eliminate one person?
Tests: proof
Can there be two celebrities under this definition?
Tests: logical reasoning

Hiring now

Flexport has 115 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer II, Autonomous Freight Technology
Bellevue, Washington, United States
Software Engineer II, DevEx
Amsterdam, Netherlands
Staff Software Engineer, DevEx
Amsterdam, Netherlands

Or practice this question first

Next question