Katkat
Back

Find the Celebrity from a Knows Matrix

OmnissaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to solve a search problem in O(N) time by utilizing the transitive and exclusionary properties of the 'knows' relationship to eliminate candidates.

Problem Statement

In a company of n people, a "celebrity" is defined as someone who is known by everyone else, but who does not know anyone else. You are given a square matrix knows of size n x n represented as a 2D array, where knows[i][j] == 1 if person i knows person j, and 0 otherwise.

Your task is to identify the celebrity's index (0 to n-1). If no celebrity exists, return -1.

Function Signature

def find_celebrity(knows: List[List[int]]) -> int:

Constraints

  • n is between 1 and 2000.
  • knows[i][i] is always 0 (a person does not know themselves).
  • knows matrix is provided as a list of lists.

Examples

Example 1: Input: [[0, 1, 0], [0, 0, 0], [0, 1, 0]] Output: 1 Explanation: Person 1 is known by 0 and 2. Person 1 knows no one.

Example 2: Input: [[0, 1], [1, 0]] Output: -1 Explanation: Person 0 knows 1, and person 1 knows 0. Neither is a celebrity.

Edge Cases

  • Single person [[0]]: Should return 0.
  • No relationships: If n > 1, return -1 unless there is a specific configuration.

Implement an algorithm that performs better than the brute-force O(n^2) check.

Hints

Hint 1

Consider that if person A knows person B, A cannot be the celebrity, but B might be.

Hint 2

You can iterate through the people once to maintain a single candidate, discarding anyone who knows someone else.

Hint 3

After finding a candidate, you must perform a second pass to verify that they satisfy both celebrity conditions (known by all, knows no one).

Follow-up questions

  • How would your approach change if you were provided an API `bool knows(a, b)` instead of the full matrix?
  • Can you prove that your algorithm is optimal in terms of time complexity?
  • How would you modify your solution to handle the case where multiple celebrities might exist (though the definition implies uniqueness)?