You are at a party with
n people.
The people are labeled from
0 to
n - 1.
Based on the celebrity rules, at most one person can be a celebrity.
A celebrity is a person who satisfies both of the following conditions:
- Every other person at the party knows the celebrity.
- The celebrity does not know any other person at the party.
Your task is to find the celebrity, or determine that no celebrity exists.
The relationship data is given as a
List<String> named
graph.
Each string represents one row of the relationship matrix.
Values inside each row are separated by commas.
If
graph.get(a) has value
1 at column
b, then person
a knows person
b.
If
graph.get(a) has value
0 at column
b, then person
a does not know person
b.
Return the celebrity label if a celebrity exists.
Return
-1 if no celebrity exists.
Class Definition
Implement the class CelebrityFinder.
Method Signature
int findCelebrityFromGraph(List<String> graph)
graph represents the hidden relationship matrix.graph.size() is the number of people at the party.- People are labeled from
0 to graph.size() - 1.
- Returns the label of the celebrity if one exists.
- Returns
-1 if no celebrity exists.
Relationship Graph
The input
graph is a
List<String>.
Each string contains exactly
n comma-separated values.
The value at row
a and column
b describes whether person
a knows person
b.
1 means person a knows person b.0 means person a does not know person b.
For example,
"1,0,1" means this row person knows person
0, does not know person
1, and knows person
2.
Celebrity Rules
For a person
c to be the celebrity:
0 ≤ c < n- For every person
i where i != c, person i must know person c.
- For every person
i where i != c, person c must not know person i.
Deterministic Output
Since there can be at most one celebrity, the output is deterministic.
Return the celebrity label if the celebrity exists.
Return -1 if the party has no celebrity.
Constraints
1 ≤ graph.size() ≤ 1000- Let
n = graph.size().
- Each row in
graph contains exactly n comma-separated values.
- Each value is either
0 or 1.
1 means the row person knows the column person.0 means the row person does not know the column person.- The value at row
i and column i does not affect whether person i is a celebrity.
Examples
Example 1
Method call:
findCelebrityFromGraph(graph = ["1,0,1,0", "1,1,1,0", "0,0,1,0", "1,0,1,1"])
Output:
2
Explanation:
Person 2 does not know any other person.
Persons 0, 1, and 3 all know person 2.
Therefore, person 2 is the celebrity.
Example 2
Method call:
findCelebrityFromGraph(graph = ["1,1,0", "0,1,1", "1,0,1"])
Output:
-1
Explanation:
No person satisfies both celebrity conditions.
Person 0 knows person 1.
Person 1 knows person 2.
Person 2 knows person 0.
Therefore, no celebrity exists.
Example 3
Method call:
findCelebrityFromGraph(graph = ["1"])
Output:
0
Explanation:
There is only one person at the party.
Since there are no other people to know or be known by, person 0 is considered the celebrity.