RANDOM PICK INDEX | LEETCODE # 398 | PYTHON RESERVOIR SAMPLING

[@smoran02]

Really missing the proof for why it works for the earlier indices. For example for the second value, probability of 1st selection is 1/2. Probability of being selected next is 1/2 * 2/3 = 1/3. Probability of being selected when you have seen 4 values is 1/2*2/3*3/4 = 1/4. This is what makes the explanation make sense

[@provarence7361]

great comment, was confused about this

[@manojamrutharaj9071]

Thank you for all these videos with easy explanations. Will be glad if we have all Hard Leetcode problems playsist.

[@kareni7572]

Found this solution and explanation more intuitive than others!

[@shuier525]

Comment from Nov 2024. Thank you for pointing out this great solution. The solution tab for this question has been disabled. This RESERVOIR sampling solution is still TLE. Without your explanation, I do not even know there is a RESERVOIR SAMPLING solution. I think the main reason is because leetcode might updated the constraint to a larger number: Constraints: 1

[@shoaibakhtar9194]

Equal possibility return explanation. So in the loop, the index closer to the start is easier to be picked, but also easier to be replaced since more iterations left behind. For example, let's say we have 5 duplicates in total. For the 2nd index, the chance it get returned is: 1/2(pick)*2/3(replace)*3/4(replace)*4/5(replace) = 1/5 with 3 iterations left; Replace probablility is calculated like this:- 2/3(replace means 2 index 1st and 3rd) can be picked and total possibilities are 1,2 and 3 indexes. So change of getting replaced is 2/3) For the 5th index, the chance it get returned is: 1/5(pick) = 1/5 , no chance to be replaced since no iterations left.

[@sourvad]

You sir, are goated

[@KiKi-lt4pf]

Awesomely explained🎉, but when you suddenly moved to coding my eyes got burnt because of the light theme😂

[@crackfaang]

Normally I hate light mode but I've done so much Leetcode over the years before they had dark mode that my brain is used to the standard theme. But yes, at work whenever I see someone's VS Code and they aren't using a dark theme I think they're a bit nuts

[@piyush10793]

This would be biased since we always have higher probability to select the first index that equals target right?

[@JAIMEAYMERICHFANS]

Not really. On the 2nd pass you have a 50 /50 chance to select the 1st and the same for the 2nd.

[@subhadipnandi294]

Very intuitive. Thank you.

[@yashmundada2483]

so this is even slower than the hashmap?

[@400racr]

i know right i feel like im taking crazy pills how is an o1 time and O(N) space LESS preferred than an o1 space O(N) time??

[@YT.Nikolay]

I solved this question using dict, I am wondering if the interviewer would like to have me implement reservoir sampling. P.S. first time I see this algorithm, worth memorizing? And again, thanks for the video! :)

[@YT.Nikolay]

I am dumb, again, I solved the problem myself and then watched the explanation. #facepalm I guess it clicked, and I would be able to solve it if ever have this on interview

[@crackfaang]

I’d say know the reservoir sampling solution. It’s quite simple and intuitive once you have seen it before. The dictionary one is too simple and if they are asking this question they probably want to see the optimal one

[@400racr]

@@crackfaang how is an O(N) time solution optimal over an O(1) solution

[@johnlabarge]

I'm confused are the numbers sorted?

[@SeanKearney-g7d]

no

[@subee128]

Thank you very much

[@SeanKearney-g7d]

reservoir sampling is cool

[@Krankschwester]

Why is this, O(N) solution, "optimal", when you can use a hashmap and answer queries in O(1)? Makes no sense.

[@erice.3892]

you have to iterate through the list to make the hashmap, which would be O(N) as well. but i see what you mean. you can store the hashmap and reuse it, therefore save time if this function is called multiple times

[@arjityadav8371]

Yes, his pick function should be optimized to retrieve in O(1) and that can only be done if he has stored the input in hashmap taking up space O(N)

[@kumarlakshya4407]

great explanation

[@annlaosun6260]

Your answer did not go through. The hash map method went through fine. I got this "time limit exceed' error using your answer. Please help....

[@ayushmusic3684]

me too

[@omaro9627]

nice

[@GoNguyen-i3k]

I don't understand the question, can anybody explain that? 😂