Find The Celebrity
MediumGraph · Adobe
There are n people at a party, labelled 0 to n - 1. You are given an n x n matrix knows where knows[a][b] == 1 means person a knows person b, and 0 means they do not. Knowing is one-directional: a knowing b says nothing about whether b knows a. Everyone knows themselves, so knows[i][i] is always 1; ignore the diagonal.
A celebrity is a person who is known by all n - 1 other people and who knows none of them. Return the label of the celebrity, or -1 if there is no celebrity. There can never be two celebrities, so the answer is unique.
Treat each lookup knows[a][b] as an expensive question you ask a guest: aim to find the answer with O(n) lookups instead of reading the whole matrix.
Example 1
- Input:
- knows = [[1, 0, 1, 0], [1, 1, 1, 0], [0, 0, 1, 0], [0, 1, 1, 1]]
- Output:
- 2
- Explanation
- Column 2 is all
1s, so everyone knows person 2, and row 2 has a1only on the diagonal, so person 2 knows nobody else. Person 2 is the celebrity.
Example 2
- Input:
- knows = [[1, 1, 0], [0, 1, 1], [1, 0, 1]]
- Output:
- -1
- Explanation
- Person 0 knows 1, person 1 knows 2 and person 2 knows 0. Everyone knows somebody, so nobody can be the celebrity.
Example 3
- Input:
- knows = [[1, 0], [1, 1]]
- Output:
- 0
- Explanation
- Person 1 knows person 0, and person 0 knows nobody else, so person 0 is the celebrity.
Constraints
n == knows.length == knows[i].length2 <= n <= 100knows[i][j]is0or1knows[i][i] == 1