528. Random Pick with Weight
https://leetcode.com/problems/random-pick-with-weight
Video Chapters:
00:00: Video Content Intro
0:08: Question Explanation
3:08: Solution Think through
6:21: Approach-1: Scaled-up Prefix Sum Solution
7:48: Coding Approach-1
8:17: Complexity Analysis of Approach-1
8:32: Approach-2: Scaled-up Prefix Sum Solution Optimized With Binary Search
8:54: Coding Approach-2
9:15 Complexity Analysis of Approach-2
Explanation of why prefixSum works:
1. Create a list of cumulative weights.
2. Choose a random integer between 1 and the sum of all weights.
3. Binary search the cumulative list for the index where the random integer
would be inserted and return that index.
4. Probability of choosing an index is proportional to its weight.
Complexity Analysis:
Time Complexity: O(logN) for pickIndexBinary function.
Space Complexity: O(1)
Link to the code: https://github.com/codewonkamentor/LeetCodeChannel
#leetcode #leetcodecoding #leetcodesolution #optimalsolution #education #codinglife #faang #interview #interviewquestions #coding #programming #codinginterview
