The Celebrity Problem
Advanced Implementation & Design DSA practice problem on Onlearn.
Difficulty: hard.
Topics: The Celebrity Problem, Arrays, Algorithm, Time Complexity, Space Complexity, Graph, Stack, Two Pointers, Brute Force, Optimization, matrix representation, stack, graph theory, time complexity analysis, two pointer technique, Graph Representation, Algorithm Optimization.
The Celebrity Problem Problem Statement In a party of N people, a celebrity is defined as someone who is known by everyone else but does not know anyone. You are given an N x N integer matrix knows, where knows[i][j] = 1 if person i knows person j, and knows[i][j] = 0 otherwise. Your task is to find the celebrity at the party. If there is no celebrity, return 1. Input Specification The first line of input contains an integer N, representing the number of people at the party. The next N lines each contain N integers, forming the knows matrix, where knows[i][j] is either 0 or 1. Output Specification Return the 0 indexed integer ID of the celebrity. If no celebrity exists, return 1. Constraints 1 <= N <= 1000 knows[i][j] is 0 or 1 knows[i][i] = 0 (A person does not know themselves) Difficulty Level Medium