I answered this question in three ways. I explained them and wrote the code. Even though I brought down the time complexity so much, the interviewer was not very professional and kept interrupting me. He also never really listened to my approach.