I didn't see you mention this, but the point of the coding interview is not to see how optimal your solution is (although it helps). It's also to see if you're a good person to work with.
If you nail the problem right away but you don't talk it through with the interviewer you'll be scored lower. They want to see if you'd be a person they'd like to work with on the team, not the quiet person that never collaborates.