Standard Bar Stack and Queues · Implementation O(n) · O(n)
At a closed-door briefing, an informant is someone everyone else can identify but who can identify no one. Guests are seated in a grid where cell (i, j) states whether guest i can identify guest j. With at most one informant possible, a two-phase sweep eliminates guests pairwise until one candidate remains, then verifies the candidate against everyone.
Input: An n x n binary matrix M where M[i][j] = 1 means person i knows person j.
Output: Return the informant's index, or -1 if no informant exists.
1 <= n <= 1000M[i][i] is irrelevant (no self-knowledge is asked)At most one informant can existInput: {"M":[[0,1,0],[0,0,0],[0,1,0]]}
Output: 1
Guests 0 and 2 both know guest 1, who knows nobody — person 1 is the informant.
Input: {"M":[[0,1],[1,0]]}
Output: -1
Each guest knows the other, so neither can be the informant.