Let me ask you this? How much time did you spend coding the sub-optimal solution?
For many of the questions I use during the interview process, I have a pretty good calibration level regarding how long it should take someone to answer a question. If the last couple of times I've used the question, the candidates were able to come up with an answer in 5 minutes, and then another candidate spends 10 minutes writing down an O(n3) solution, and then tries to come up with an more optimal solution, it might be understandable why I might give that last candidate a somewhat lower score.
One thing that can help is to also keep talking so the interviewer knows what you are thinking. That way if you outline an O(n2) solution very quickly, and then say, I think I can get a O(n log n) solution this other way, then you're showing your work, and it's a lot easier to get partial credit on a question.
In general it's better to explain the approach you want to take before you start coding. If an interviewer knows that you're going off in the weeds, perhaps because you misunderstood the problem, that will be an opportunity for the interviewer to clarify the problem, and perhaps give you a hint to steer you in the right direction. (Remember, most of the time the interviewer has used this question multiple times in the past, so s/he know where people are likely to get stuck, and very likely has hints prepared if people stumble --- and one or two stumbles does not a No Hire make; the goal is to see how someone codes and how they think, you don't get a 0 or 1 grade.)
For many of the questions I use during the interview process, I have a pretty good calibration level regarding how long it should take someone to answer a question. If the last couple of times I've used the question, the candidates were able to come up with an answer in 5 minutes, and then another candidate spends 10 minutes writing down an O(n3) solution, and then tries to come up with an more optimal solution, it might be understandable why I might give that last candidate a somewhat lower score.
One thing that can help is to also keep talking so the interviewer knows what you are thinking. That way if you outline an O(n2) solution very quickly, and then say, I think I can get a O(n log n) solution this other way, then you're showing your work, and it's a lot easier to get partial credit on a question.
In general it's better to explain the approach you want to take before you start coding. If an interviewer knows that you're going off in the weeds, perhaps because you misunderstood the problem, that will be an opportunity for the interviewer to clarify the problem, and perhaps give you a hint to steer you in the right direction. (Remember, most of the time the interviewer has used this question multiple times in the past, so s/he know where people are likely to get stuck, and very likely has hints prepared if people stumble --- and one or two stumbles does not a No Hire make; the goal is to see how someone codes and how they think, you don't get a 0 or 1 grade.)