algoadvance

Leetcode 398. Random Pick Index

Problem Statement

You are given an integer array nums with possible duplicates. You want to design an algorithm that randomly picks an index of a given target number. Implement the Solution class:

• Solution(int[] nums) Initializes the object with the array nums.
• int pick(int target) Picks a random index i from nums where nums[i] == target. If there are multiple valid i’s, each index should have an equal probability of being returned.

Clarifying Questions

1. What are the constraints on the nums array?
   • The array nums will have a length of up to 50,000.
   • Each element in nums can be between -1,000,000 and 1,000,000.
2. How often will the pick function be called relative to the initialization?
   • The pick function may be called multiple times after the Solution object is initialized.
3. Is there any restriction on the runtime and space complexity of the solution?
   • The initialization can take some time (ideally linear), but the pick function should be optimized for efficiency, ideally constant time.

Strategy

To solve this problem, we’ll use Reservoir Sampling, a technique used to randomly choose k samples from a list of n items, where n is either a very large or unknown number.

1. Initialization (Solution constructor):
   • Simply store the array nums.
2. Random index selection (pick function):
   • Use Reservoir Sampling to randomly pick one index from the potential candidates.

Explanation of Reservoir Sampling for this problem:

• Traverse through the array nums. For each index i where nums[i] equals the target, choose that index with a certain probability.
• The probability is 1/count where count is the number of valid indices seen so far.

This ensures that each valid index has an equal probability of being chosen.

Code

#include <vector>
#include <cstdlib>
#include <ctime>

class Solution {
private:
    std::vector<int> nums;

public:
    Solution(std::vector<int>& nums) {
        this->nums = nums;
        std::srand(std::time(0)); // Initialize random number generator
    }
    
    int pick(int target) {
        int chosen_index = -1;
        int count = 0;
        
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == target) {
                ++count;
                if (std::rand() % count == 0) { // Probability of 1/count
                    chosen_index = i;
                }
            }
        }
        
        return chosen_index;
    }
};

Time Complexity

1. Initialization: O(n) where n is the length of the nums array.
   • This is only to store the array, so it’s efficient.
2. Pick Function:
   • The pick function runs in O(n) where n is the length of the nums array.
   • Despite this, Reservoir Sampling is efficient in choosing the index by traversing the array only once.

Summary

• Used Reservoir Sampling to ensure an equal probability for each valid index.
• Initialization is efficient and the pick function, although it has linear time complexity with respect to the size of the input array, is optimized for scenarios with multiple valid targets.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?