To be honest, I had forgotten the O(n) solution and vaguely remembered the nlogn solution. After that experience, I have both solutions lodged in my brain.