Random Pick with Weight

Problem Summary

What is Being Asked?

(One sentence on the actual task.)

Key Observations

(Patterns, constraints, or hints in the problem statement.)

Approach Taken

(Step-by-step logic or pseudocode before coding.)

Why This Works

(Explain the core reason the solution is correct.)

Main Concepts Used

(Mark the CS concepts or algorithms used.)

Time & Space Complexity

• Time: $O()$ → Reason:
• Space: $O()$ → Reason:

Code

class Solution:
    def __init__(self, w: List[int]):
        self.cum_weight = []
        self.total = 0
        for weight in w:
            self.total += weight
            self.cum_weight.append(self.total)

    def pickIndex(self) -> int:
        random_num = random.randint(1, self.total)

        l, r = 0, len(self.cum_weight) - 1
        while l <= r:
            m = (l + r) // 2
            mid = self.cum_weight[m]

            if mid == random_num:
                return m
            elif mid > random_num:
                r = m - 1
            else:
                l = m + 1
        return l

Common Mistakes / Things I Got Stuck On