166. The Celebrity Problem

There are n people at a party. A celebrity is someone everyone else knows, but who knows no one else. Given an n x n matrix where knows[i][j] = 1 means person i knows person j, find the celebrity's index (0-indexed), or print -1 if there is none. It's guaranteed at most one celebrity can exist.

Input: The first line contains an integer n. Each of the next n lines contains n space-separated integers (0 or 1) - the knows matrix. Output: Print a single integer - the 0-indexed celebrity, or -1 if none exists.

1 <= n <= 1000

The FINAL verification step is not optional - the elimination process only ever narrows down to ONE SURVIVING candidate, but doesn't guarantee that candidate is actually a genuine celebrity (there might be NO celebrity at all), which is exactly why an explicit final check against everyone is required.

Among n people, find the one 'celebrity' - someone everyone else knows, but who knows nobody else themselves. Brute force: Check every person against every other person directly (is X known by everyone, and does X know no one) - this costs O(n²), examining the full matrix, when a smarter elimination process can find the ONE viable candidate using far fewer comparisons. Optimised: Since AT MOST ONE celebrity can exist, comparing any two candidates directly ELIMINATES one of them for certain (whoever knows the other definitely isn't the celebrity) - repeating this elimination via a stack narrows n candidates down to just 1 in O(n) comparisons, with only a final O(n) verification pass needed afterward.

For each person i, scan their entire row and column of the matrix: i is a celebrity only if knows[i][j] is 0 for every j != i (knows no one) and knows[j][i] is 1 for every j != i (everyone knows them). Checking every candidate this way costs O(n) work per candidate, and there are n candidates, so the whole matrix effectively gets scanned for each person. This is correct by definition but redundantly re-examines rows/columns that could already rule out most candidates earlier. Time: O(n^2) Space: O(1)

Push all n people onto a stack. Repeatedly pop the top two people a and b: if a knows b, then a cannot be the celebrity (a celebrity knows no one) so discard a and push b back; otherwise b cannot be the celebrity so discard b and push a back. After this elimination only one candidate remains on the stack; verify that candidate against the full matrix in O(n). This avoids blindly checking every person's full row and column up front, narrowing to a single candidate first. Time: O(n) Space: O(n)

Replace the stack with a single running candidate variable, avoiding any extra memory. Start with candidate = 0, and for each next person i from 1 to n-1, if candidate knows i then i replaces candidate as the new potential celebrity, otherwise candidate is kept and i is discarded (the same elimination logic as the stack version, just done in place). Once a single candidate remains, verify it against the full matrix in one O(n) pass. This achieves the same linear time as the stack approach but with only constant extra space. Time: O(n) Space: O(1)

1. Push every person onto a stack as a candidate. 2. Repeatedly pop TWO candidates a and b: check if a knows b - if so, a CANNOT be the celebrity (a celebrity knows no one), so discard a and keep b as the surviving candidate; otherwise, discard b and keep a. 3. After narrowing down to just ONE final candidate, VERIFY it directly against everyone: it must be known by ALL others and know NONE of them.

Time: O(n) - n-1 elimination comparisons to narrow down to one candidate, plus O(n) to verify that final candidate. Space: O(n), for the stack of candidates.

n = 1 (that person is trivially the celebrity); a matrix where the elimination process leaves a candidate that still fails verification (answer -1); n up to 1000 for performance.

Be ready to explain WHY comparing any two candidates always safely eliminates exactly one of them - this elimination-based reduction (from O(n²) all-pairs checking down to O(n) total) is the entire clever insight behind this classic problem.