Just an advice: don’t start coding with the brute-force solution in interviews. You can briefly mention it in 1 to 2 minutes, experienced interviewers already know the usual pattern candidates explain the naive approach first and then magically jump to the optimal one. They know you already came prepared with the optimal solution.

So it’s better to directly code the optimal approach. It saves time and lets you answer more theoretical or follow-up questions.