While what you say is the ideal situation, I think being able to get the optimal solution and giving at least a halfway decent explanation about why it works is the #1 most important thing (along with just plain old not being a jerk).

I acknowledge there are some situations where you might pass the interview even without arriving at the optimal solution, but those are probably the exceptions.