LeetCode 398: Random Pick Index Solution in Python – A Step-by-Step Guide

What Is LeetCode 398: Random Pick Index?

In LeetCode 398: Random Pick Index, you’re given an array of integers nums that might have duplicates, and you need to design a class that can randomly pick an index of a given target number. Each index where the target appears should have an equal chance of being picked. For example, with nums = [1, 2, 3, 3, 3] and target 3, calling the pick function might return 2, 3, or 4, each with a 1/3 chance. It’s like a raffle where every matching ticket gets a fair shot at winning!

Problem Statement

• Input: An integer array nums (in the constructor), and a target integer target (in the pick method).
• Output: An integer—randomly chosen index where nums[index] == target.
• Rules:
• Equal probability for each valid index.
• Solution must handle duplicates.

Constraints

• 1 <= nums.length <= 2 * 10⁴.
• -10⁹ <= nums[i] <= 10⁹.
• pick called at most 10⁴ times.
• target exists in nums.

Examples

• Input: nums = [1, 2, 3, 3, 3], target = 3
• Output: 2, 3, or 4 (randomly, 1/3 chance each).
• Input: nums = [1, 2, 3, 4], target = 3
• Output: 2 (only one 3).
• Input: nums = [1, 1, 1, 1], target = 1
• Output: 0, 1, 2, or 3 (1/4 chance each).

Understanding the Problem: Picking Randomly

To solve LeetCode 398: Random Pick Index in Python, we need a class that takes an array in its constructor and has a pick method to return a random index for a target number. The catch? If the target appears multiple times, each index must have an equal shot. A simple idea might be to find all indices and pick one—but what if the array’s huge and we don’t want to store extra stuff? We’ll use:

• Best Solution (Reservoir Sampling): O(n) time per pick, O(1) space—clever and light.
• Alternative Solution (Hash Map): O(1) time per pick, O(n) space—easy but heavy.

Let’s dive into the reservoir sampling solution with a clear, step-by-step explanation.

Best Solution: Reservoir Sampling

Why This Is the Best Solution

Reservoir sampling is the star here because it’s efficient—O(n) time per pick with O(1) space. It doesn’t need to store a list of indices upfront, making it perfect for huge arrays or streams of data. It’s like picking a winner from a raffle without writing down every ticket—just a smart way to roll the dice as you go!

How It Works

Let’s imagine we’re picking a winner from a line of people holding numbers:

• Step 1: Walk Through the Array:
• Look at each spot in nums, checking if it matches the target.
• Step 2: Keep a Running Choice:
• When you find the first match, pick that index—it’s your “current winner.”
• For each later match, roll a dice to decide if it replaces the current winner, with a chance that shrinks as you find more matches.
• Step 3: Equal Odds Magic:
• If there are k matches total, each should have a 1/k chance.
• For the first match, pick it (1/1 chance).
• Second match: keep first with 1/2, pick second with 1/2.
• Third match: keep current with 2/3, pick third with 1/3.
• This balances out so every index ends up with 1/k odds.
• Step 4: Why This Works:
• It’s a streaming trick: you don’t need all matches at once.
• The probability math ensures fairness without extra storage.
• It’s like a game where each new player has a fair shot to win, adjusted by how many came before.

It’s a clever way to pick randomly without holding everything in your head!

Step-by-Step Example

Example: nums = [1, 2, 3, 3, 3], target = 3

• Setup: Indices with 3 are 2, 3, 4 (3 matches total, 1/3 chance each).
• Walk Through:
• Index 0: 1 ≠ 3, skip.
• Index 1: 2 ≠ 3, skip.
• Index 2: 3 = 3, first match, pick 2 (count = 1, chance = 1/1).
• Index 3: 3 = 3, second match (count = 2):
• Random 0 or 1 (0 to 1-1), if 0 (1/2 chance), pick 3, else keep 2.
• Say we keep 2.
• Index 4: 3 = 3, third match (count = 3):
• Random 0 or 1 or 2 (0 to 2-1), if 0 (1/3 chance), pick 4, else keep 2.
• Say we pick 4.
• Result: Returns 4 (could’ve been 2 or 3, each 1/3 likely).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def __init__(self, nums: List[int]):
        # Step 1: Store the array
        self.nums = nums

    def pick(self, target: int) -> int:
        # Step 2: Set up variables
        count = 0  # How many matches we’ve seen
        chosen = 0  # The current picked index

        # Step 3: Walk through the array
        for i in range(len(self.nums)):
            # If we find the target
            if self.nums[i] == target:
                count += 1  # One more match
                # Randomly decide if this index wins
                if random.randint(0, count - 1) == 0:
                    chosen = i  # Pick this index

        return chosen

• Line 2-4: Constructor:
• Save nums so we can use it in pick.
• Line 6-17: pick method:
• Line 8-9: Start with 0 matches and a placeholder index.
• Line 12-16: Loop through the array:
• Line 13-14: If the number matches the target, increase count.
• Line 15-16: Generate a random number from 0 to count-1. If it’s 0 (1/count chance), pick this index. E.g., second match: 0 or 1, 1/2 chance to pick.
• Line 18: Return the final chosen index.
• Time Complexity: O(n)—one pass through the array.
• Space Complexity: O(1)—just two variables (array is input).

This is like a raffle where each ticket gets a fair shake as you go!

Alternative Solution: Hash Map with Random Selection

Why an Alternative Approach?

The hash map method stores all indices for each number upfront, then picks randomly when asked. It’s O(1) time per pick but O(n) space—simple and fast for picking, but it needs more memory. It’s like writing down every ticket in a jar before drawing one!

How It Works

Picture it as a lookup table:

• Step 1: Build a map where each number points to a list of its indices.
• Step 2: For a target, grab its list and pick a random index from it.
• Step 3: Return that index.

Step-by-Step Example

Example: nums = [1, 2, 3, 3, 3], target = 3

• Build Map: {1: [0], 2: [1], 3: [2, 3, 4]}.
• Pick 3: Get [2, 3, 4], randomly choose one (e.g., 3).
• Result: 3 (could be 2 or 4).

Code for Hash Map Approach

Copy codeclass Solution:
    def __init__(self, nums: List[int]):
        # Build map of number to indices
        self.map = {}
        for i in range(len(nums)):
            if nums[i] not in self.map:
                self.map[nums[i]] = []
            self.map[nums[i]].append(i)

    def pick(self, target: int) -> int:
        # Pick random index from target’s list
        indices = self.map[target]
        return random.choice(indices)

• Time Complexity: O(n) for constructor, O(1) per pick.
• Space Complexity: O(n)—stores all indices.

It’s a prepped jar of tickets!

Comparing the Two Solutions

• Reservoir Sampling (Best):
• Pros: O(n) pick, O(1) space, no prep.
• Cons: Linear time per pick.
• Hash Map (Alternative):
• Pros: O(1) pick, O(n) space, fast picks.
• Cons: Heavy memory.

Reservoir wins for space.

Additional Examples and Edge Cases

• [1], 1: 0 (one index).
• [2, 2], 2: 0 or 1 (1/2 each).
• [1, 1, 1], 1: 0, 1, or 2 (1/3 each).

Reservoir handles all.

Complexity Breakdown

• Reservoir Sampling: Time O(n) per pick, Space O(1).
• Hash Map: Time O(n) init, O(1) pick, Space O(n).

Reservoir’s lean.

Key Takeaways

• Reservoir Sampling: Stream and pick!
• Hash Map: Store and choose!
• Randomness: Fairness is key.
• Python Tip: Random rocks—see [Python Basics](/python/basics).

Final Thoughts: Roll the Dice

LeetCode 398: Random Pick Index in Python is a randomness challenge. Reservoir sampling picks lean and mean, while hash maps prep for speed. Want more random fun? Try LeetCode 384: Shuffle an Array or LeetCode 382: Linked List Random Node. Ready to pick? Head to Solve LeetCode 398 on LeetCode and roll that dice today!