10277. Find the Celebrity

Imagine you are at a gathering with n guests (numbered from 0 to n - 1). Among these guests, there might be one "star guest" - someone who is known by every other guest but does not know anyone else at the party.

Your task is to determine if such a "star guest" exists, or confirm that there is none. You can only get information by asking questions like: "Does person A know person B?" To minimize the number of queries, you are given access to a helper function boolean knows(int x, int y) that returns true if person x knows person y.

Write a method int findStarGuest(int n) that returns the label of the star guest if one exists, or -1 if there is no such person.

Examples

Example 1:
Input: guests = [
  "1 1 0",
  "0 1 0",
  "1 1 1"
]
Output: 1
Explanation: There are three people (0, 1, 2). guests[i][j] = 1 means person i knows person j, and 0 means they do not. The star guest is person 1 because both 0 and 2 know 1, but 1 knows no one (other than themselves).

Example 2:
Input: guests = [
  "0 0 1",
  "1 1 0",
  "0 1 1"
]
Output: -1
Explanation: No one fits the star guest criteria in this case.

Constraints

  • 2 ≤ n ≤ 200
  • Each row of the guests array is a string of '0's and '1's separated by spaces, representing who knows whom.
  • There can be at most one star guest at the party.




Please use Laptop/Desktop or any other large screen to add/edit code.