#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/meta-interview-prep-v2/coding-patterns-ii-trees-graphs-advanced/leetcode-528-random-pick-with-weight-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/meta-interview-prep-v2/coding-patterns-ii-trees-graphs-advanced/leetcode-528-random-pick-with-weight-implementation

Repovive

LeetCode 528 Random Pick with Weight - Implementation - Coding Patterns II: Trees, Graphs & Advanced | Meta Interview Prep | Repovive

Repovive.

Meta Interview Prep6 sections · 147 units8h total

Open in Course

LeetCode 528 Random Pick with Weight - Implementation

The approach

class Solution:
    def __init__(self, w):
        self.prefixSums = []
        runningTotal = 0
        for weight in w:
            runningTotal += weight
            self.prefixSums.append(runningTotal)
        self.totalWeight = runningTotal

    def pickIndex(self):
        target = random.randint(1, self.totalWeight)
        left = 0
        right = len(self.prefixSums) - 1
        while left < right:
            mid = (left + right) // 2
            if self.prefixSums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

$O(n)$ init time and space. $O(\log n)$ per pick.