How to Answer in an Interview

You are not being marked on whether you produce the optimal solution. You are being marked on whether working with you would be pleasant and productive. Those are different tests, and the second one is easier to pass.

The sequence

1. Restate the problem. One sentence. It catches misunderstandings while they are still free.
2. Ask about the edges. Empty input? Duplicates? Negative numbers? Is it sorted? How large can it get?
3. Say the brute force out loud, with its complexity. "I could check every pair, that is O(n squared)." You now have a working answer banked.
4. Name the bottleneck. "The inner loop repeats a search I could do in constant time."
5. Improve that one thing, and say what it costs. "A hash map makes it O(n) time and O(n) space."
6. Then write the code.
7. Test it out loud on a small case and an edge case.

Most people skip steps 1 to 5 and start at 6. That is why they solve the wrong problem, or freeze.

Say the complexity unprompted

Every solution should come with its cost, stated without being asked:

"This is O(n) time and O(n) space. I could get to O(1) space with two pointers if the array were sorted, but sorting would make it O(n log n) overall, so this is better unless the input arrives sorted."