Algorithm solves 'celebrity problem' efficiently with linear time

The celebrity problem asks to identify a person in a group whom everyone knows but who knows no one else. It is typically represented by an n x n matrix where entries indicate whether one person knows another. A naive brute-force solution requires O(n²) time to check all relationships. However, a more efficient algorithm can find a potential candidate in O(n) time using a single pass, then verify the candidate with a second pass. This optimized approach uses constant extra memory, improving on earlier stack-based linear-time methods.