FastPrepFind the Celebrity
Problem · Array

Find the Celebrity

Learn this problem
● MediumOmnissa logoOmnissaFULLTIMEONSITE INTERVIEW

Problem statement

A group contains n people numbered from 0 through n - 1. You are given an n × n matrix knows: knows[a][b] = 1 means person a knows person b, and 0 means they do not.

A celebrity is known by every other person and knows no other person. Return the celebrity's index, or -1 when no celebrity exists. Diagonal entries are ignored. With one person, return 0.

Optimize the number of matrix lookups after the input is available. Matrix indexing provides the relation queries used in the interview.

Function

findCelebrity(knows: int[][]) → int

Examples

Example 1

knows = [[0,0,1],[1,0,1],[0,0,0]]return = 2

People 0 and 1 know person 2, while person 2 knows neither of them.

Example 2

knows = [[1,1],[1,0]]return = -1

Each person knows the other, so neither is a celebrity. The diagonal values have no effect.

Constraints

  • 1 <= n <= 50
  • knows.length = n, and every row has length n.
  • Every entry is 0 or 1.

More Omnissa problems

drafts saved locally
public int findCelebrity(int[][] knows) {
    // Write your code here
}
knows[[0,0,1],[1,0,1],[0,0,0]]
expected2
checking account