Find the Celebrity algorithm in linear time and constant space


I was working on this problem with various options like graph, recursion etc… however the most optimized solution I case across was using Stack which solves the problem in linear time however the space consumption was also linear.

Tried removing the stack and with simple change the space complexity changed to constant while keeping time complexity linear.

Below is the sample code.

celebrity_problem

 

Advertisements