Random Pick with Weight | random pick with weight | random pick with weight leetcode | leetcode 528
Link to code (Linear Search): https://pastebin.com/DjzEEKbs
Link to code (Binary Search): https://pastebin.com/K0aARzzt
Music: https://www.bensound.com
*Complexity Analysis*
Let N be the length of the input list.
For linear solution :
Time Complexity
For the constructor function, the time complexity would be O(N), which is due to the construction of the w_sum array.
For the pickIndex() function, its time complexity would be O(N) as well, since we did a linear search on the w_sum array.
For binarySearch Solution :
Time Complexity
For the constructor function, the time complexity would be O(N), which is due to the construction of the w_sum array.
For the pickIndex() function, this time its time complexity would be O(logN) since we did a binary search on the w_sum array.