I think your answer is technically correct. The request was space complexity ˋO(n)ˋ, which does not mean in-place.
I think these kinds of questions get much harder than they really are when you're nervous, under time constraints, and using a ridiculous medium for coding like a whiteboard.
I had the problem too. I was asked for a data structure that (these requirements were impicit in a use case that I won't repeat)
I figured it out fairly easily on the train ride home afterwards, but that's a little late...