Narrate the approach before the code
Before you type, talk through what you understand, the brute-force idea, and why it is too slow. Then propose the optimisation. This lets the interviewer course-correct you early — a small nudge at minute three saves a dead end at minute twenty.