How do you solve Random Pick Index on LeetCode?

Random Pick Index (LeetCode #398) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Reservoir sampling allows for efficient random selection.

What is the brute force solution for Random Pick Index?

The brute force approach for Random Pick Index is Brute Force, with O(n) time complexity and O(n) space complexity. The brute force approach involves iterating through the entire array to collect all indices of the target number. Then, we randomly select one of these indices. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Random Pick Index?

Random Pick Index uses the following concepts: Hash Table, Math, Reservoir Sampling, Randomized. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Random Pick Index?

Clarify the problem constraints before coding. Discuss your thought process and approach before jumping into code. Test your solution with edge cases during the interview.

What are common mistakes when solving Random Pick Index?

Not considering equal probability for all indices. Using a fixed-size array for indices instead of a dynamic structure.

#398

Random Pick Index

Medium

Hash TableMathReservoir SamplingRandomizedHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses reservoir sampling, which allows us to select an index of the target number in a single pass through the array. This ensures that we maintain equal probability for each index.

⚙️

Algorithm

3 steps

1Step 1: Initialize a variable to store the result index and a counter for occurrences of the target.
2Step 2: Iterate through the array. For each element, if it matches the target, increment the counter and randomly decide whether to update the result index.
3Step 3: Return the result index after completing the iteration.

solution.py15 lines

1import random
2
3class Solution:
4    def __init__(self, nums):
5        self.nums = nums
6
7    def pick(self, target):
8        result = -1
9        count = 0
10        for i, num in enumerate(self.nums):
11            if num == target:
12                count += 1
13                if random.randint(0, count - 1) == 0:
14                    result = i
15        return result

ℹ

Complexity note: The time complexity is O(n) because we traverse the array once. The space complexity is O(1) since we only use a few extra variables, regardless of input size.

1Reservoir sampling allows for efficient random selection.
2Understanding the problem constraints helps in designing the solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.