What is the time complexity of Random Pick with Weight?

The optimal solution has a time complexity of O(log n).

What data structures are used to solve Random Pick with Weight?

This problem uses Array, Math, Binary Search, Prefix Sum, Randomized. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Random Pick with Weight?

Insight 1: Using prefix sums allows for efficient binary search to determine the index corresponding to a randomly generated number within the total weight range. Insight 2: Employing binary search optimizes the `pickIndex` function to achieve a logarithmic time complexity.

Which companies ask LeetCode 528. Random Pick with Weight in interviews?

This problem is frequently asked at Coinbase, Criteo, Liftoff, Netflix, PayPal and 10 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Random Pick with Weight - LeetCode 528 Solution

Random Pick with Weight - Complete Solution Guide

Random Pick with Weight is LeetCode problem 528, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i th index. You need to implement the function pickIndex() , which randomly picks an index in the range [0, w.length - 1] ( inclusive ) and returns it. The probability of picking an index i is w[i] / sum(w) . For example, if w = [1, 3] , the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25% ), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75% ). Example 1: Input ["Sol

Detailed Explanation

The problem requires us to implement a `pickIndex()` function that randomly selects an index from an array `w` of positive integers. Each integer `w[i]` represents the weight or probability of picking index `i`. The probability of selecting index `i` is proportional to its weight, specifically `w[i] / sum(w)`. In other words, indices with higher weights are more likely to be selected. The constructor takes the array `w` as input and the `pickIndex` function must return a randomly chosen index based on the given weights.

Solution Approach

The solution utilizes the prefix sum technique and binary search. First, the constructor calculates the prefix sums of the input weight array `w`. The prefix sum at index `i` represents the sum of weights from index 0 to `i`. This transforms the problem of picking an index based on weight into a problem of finding which range a random number falls into. Then, when `pickIndex()` is called, a random integer between 1 and the total sum of all weights is generated. Binary search is then used on the prefix sums array to find the first index whose prefix sum is greater than or equal to the random number. This index is then returned as the selected index.

Step-by-Step Algorithm

Step 1: **Constructor (`__init__` in Python, `Solution` in Java/C++)**: Calculate the prefix sums of the weight array `w`. Store these prefix sums in a separate array (`prefix_sums`). Also, calculate and store the total sum of all weights in `total_sum`.
Step 2: **`pickIndex()`**: Generate a random integer `target` between 1 and `total_sum` (inclusive). In C, seed the random number generator in the constructor.
Step 3: **Binary Search**: Perform binary search on the `prefix_sums` array to find the smallest index `i` such that `prefix_sums[i]` is greater than or equal to `target`.
Step 4: **Return Index**: Return the index `i` found in the binary search.

Key Insights

Insight 1: Using prefix sums allows for efficient binary search to determine the index corresponding to a randomly generated number within the total weight range.
Insight 2: Employing binary search optimizes the `pickIndex` function to achieve a logarithmic time complexity.
Insight 3: Precalculating and storing the prefix sums avoids redundant calculations in each `pickIndex` call.

Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(n)

Topics

This problem involves: Array, Math, Binary Search, Prefix Sum, Randomized.

Companies

Asked at: Coinbase, Criteo, Liftoff, Netflix, PayPal, Remitly, Revolut, Rubrik, Shopee, Snap, Snowflake, Sony, Two Sigma, X, Yelp.

Random Pick with Weight | LeetCode 528

Medium

Array Math Binary Search Prefix Sum Randomized

Time: O(log n)Space: O(n)

Solution Code

Available in:

import java.util.Arrays;
import java.util.Random;

class Solution {

    private int[] prefixSums;
    private int totalSum;
    private Random random;

    public Solution(int[] w) {
        prefixSums = new int[w.length];
        int currentSum = 0;
        for (int i = 0; i < w.length; i++) {
            currentSum += w[i];
            prefixSums[i] = currentSum;
        }
        totalSum = currentSum;
        random = new Random();
    }
    
    public int pickIndex() {
        int target = random.nextInt(totalSum) + 1;
        int low = 0;
        int high = prefixSums.length;

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (prefixSums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.pickIndex();
 */

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 528: Random Pick with Weight - Detailed explanation and solution approaches.

Topics

Array Math Binary Search Prefix Sum Randomized

Companies

CoinbaseCriteoLiftoffNetflixPayPalRemitlyRevolutRubrik

Stats

Difficulty:Medium

Languages:4

Companies:15

Problem #:528

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
Step 1: **Constructor (`__init__` in Python, `Solution` in Java/C++)**: Calculate the prefix sums of the weight array `w`. Store these prefix sums in a separate array (`prefix_sums`). Also, calculate and store the total sum of all weights in `total_sum`.
2
Step 2: **`pickIndex()`**: Generate a random integer `target` between 1 and `total_sum` (inclusive). In C, seed the random number generator in the constructor.
3
Step 3: **Binary Search**: Perform binary search on the `prefix_sums` array to find the smallest index `i` such that `prefix_sums[i]` is greater than or equal to `target`.
4
Step 4: **Return Index**: Return the index `i` found in the binary search.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(log n)

🚀 Logarithmic - Very efficient! Halves the problem each step.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is determined by the `pickIndex` function which performs a binary search of size 'n', hence O(log n). The space complexity is determined by the size of the prefix sums array, which stores 'n' elements, leading to O(n).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Linear Search

Instead of binary search, we could iterate through the prefix sums array linearly. For each index, we check if the random number is less than or equal to the prefix sum at that index. If so, we return the index.

Time: O(n)Space: O(n)

Trade-offs: Linear search is simpler to implement, but it has a higher time complexity of O(n) compared to binary search's O(log n). It's only beneficial for very small input arrays where the constant factors of binary search might outweigh the logarithmic advantage.

✨

Key Insights

1Insight 1: Using prefix sums allows for efficient binary search to determine the index corresponding to a randomly generated number within the total weight range.
2Insight 2: Employing binary search optimizes the `pickIndex` function to achieve a logarithmic time complexity.
3Insight 3: Precalculating and storing the prefix sums avoids redundant calculations in each `pickIndex` call.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Edge Cases

Edge case 1: `w.length = 1`. The solution still works correctly. The prefix sum array will contain only one element, equal to the weight. The random number will always be between 1 and that weight, and the binary search will always return index 0.
Edge case 2: Large weight values. The `total_sum` could become very large. The provided solution handles this fine as the `prefix_sums` and `total_sum` are integer data types. It's within constraints given in the problem.
Edge case 3: All weights are the same. The solution correctly handles this because binary search will still converge on the appropriate index based on the random number generated.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not seeding the random number generator. Without seeding (especially in C), the same sequence of random numbers will be generated each time, leading to the same indices being picked.

✗Common mistake 2: Generating a random number between 0 and `total_sum` instead of 1 and `total_sum`. This can lead to incorrect index selection.

✗Common mistake 3: Incorrect binary search implementation, which may result in the wrong index being selected. Specifically failing to account for cases when the target is equal to one of the prefix sums.

✗Common mistake 4: Not understanding the problem statement that the probability of picking an index `i` is `w[i] / sum(w)`.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Load balancing in a distributed system. Servers can be assigned weights based on their capacity, and requests can be randomly routed to servers according to these weights.

🏦Real-world scenario 2: A/B testing. Different versions of a website or app can be shown to users with different probabilities (weights) to determine which version performs better.

🎮Real-world scenario 3: Weighted random sampling. Selecting a subset of data points from a larger dataset with probabilities proportional to their importance or relevance.

📱Real-world scenario 4: Simulation - simulating real life events which are not equally likely to occur. For example, simulating traffic patterns with different routes having different probabilities based on road size and traffic density.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 16, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Random Pick with Weight"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether math techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?