tag:blogger.com,1999:blog-4731036105252322780.post1550304369685859845..comments2024-03-01T02:55:58.951-08:00Comments on Buttercola: Leetcode: Find the Celebrity Butter is looking for a jobhttp://www.blogger.com/profile/01481083468821703855noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-4731036105252322780.post-26265736057072751452020-05-23T23:33:56.350-07:002020-05-23T23:33:56.350-07:00This question can be solved using graphs (indegree...This question can be solved using graphs (indegree and outdegree concept) in O(N^2) Time complexity.<br /><br />We can also solve this question in O(N) time and O(1) space using a simple two-pointer concept. We are going to compare two persons at a time one from beginning and other from the end and we will remove that person from consideration which cannot be a celebrity. For example, if there are two persons X and Y and X can identify person Y then surely X cannot be a celebrity as it knows a person inside this party. Another case would be when X does not know Y and in this case, Y cannot be a celebrity as there is at least one person who does not know him/her inside a party. Using this intuition two-pointer concept can be applied to find the celebrity inside this party.<br /><br />You can refer to this video for a better explanation.<br /><br />Video Link:<br /><br />https://youtu.be/aENYremq77IAnonymoushttps://www.blogger.com/profile/04596756711528043143noreply@blogger.com