Hey Everyone,

I recently had an screening interview at Google, which I passed but in the feedback they said I did not provide the optimal solution. I was wondering what is the optimal solution to that problem:
Imagine you are given a stream of non-negative integers, until you receive a zero and in that case you need to print a number from the stream with the distribution of the numbers in the stream.
i.e: [1,2,3,1,1,3,0] will have the probabilities array [0.5, 1/6, 2/6] and we have to pick a random number from that.
The solutions I proposed were:

1. Naive solution - save all the number of the stream in an array and then just pick a random index from that array. Space Complexity - O(n) , Time - O(1)
2. Optimizing Space - since there might be many duplicates to that array, I propesed that we just keep a counter (hashmap) where the keys are the integers and the values are the counts, than create probabilities array (for the previous example : [0,0.5,0.5+1/6, 1]) than randomize a number using uniform distribution [0,1) and binary search for the number in the probabilities array: Space Complexity - O(m) where m is the unique integers in the stream (worst case O(n)) , Time - O(m) because we need to create the probabilities array.

Is there any third solution which is more optimized than the second one ? I thought about creating the probabilities on the fly but I wasn't able to make it work.
The question itself does feel a little bit like this one - https://leetcode.com/problems/random-pick-with-weight/description/ the only difference is the stream

Thanks for you help :)