FastPrep
Problem · Array

Find the Celebrity from Pairwise Acquaintances

Learn this problem
● MediumSalesforce logoSalesforceFULLTIMEONSITE INTERVIEW
See Salesforce hiring insights

Problem statement

A group contains n people numbered from 0 to n - 1. The matrix entry knows[a][b] is 1 exactly when person a knows person b.

A celebrity is known by every other person but knows no other person. At most one celebrity exists. Return the celebrity's index, or -1 if the group has no celebrity. Diagonal entries are irrelevant.

Function

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

Examples

Example 1

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

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

Example 2

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

Each person knows the other, so neither can be a celebrity.

Example 3

knows = [[1]]return = 0

With one person, all off-diagonal celebrity conditions hold vacuously.

Constraints

  • 1 <= n <= 2000.
  • knows is an n x n matrix.
  • Every entry is 0 or 1.
  • Only off-diagonal entries determine the result.

More Salesforce problems

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