Random Pick Index LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon ByteDance Facebook Google MicrosoftViews 1624

Problem Statement

Random Pick Index LeetCode Solution- We are given a constructor of class “Solution” and a function “pick” of type int. We are required to implement the “Solution” class as

  • 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, then each index should have an equal probability of returning.

Example and Explanation

Input
[“Solution”, “pick”, “pick”, “pick”]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

Explanation
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(1); // It should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.

Approach

This question is based on pure implementation. To allow variable accessibility in all the functions in the Solution class let us define an empty array or vector ‘a’ outside the constructor.

For initialization in Solution(), simply assign the value of nums to the predefined empty array ‘a’.

Now, for the pick() function, iterate through all the values in ‘a’ and store the index of the target into another temporary empty array ‘temp’. To make all indexes of ‘target’ equally likely, let us use the basic concept of probability. First, find the size of array ‘temp’ and use a random function that returns any value from 0 to temp_size-1. Since the random function returns values with equal probability, it suffices our question constraint.

Code

C++ code for Random Pick Index

class Solution {
    vector<int> a;
public:
    Solution(vector<int>& nums) {
        a=nums;
    }
    
    int pick(int target) {
        vector<int> temp;
        for(int i=0; i<a.size(); i++) {
            if(target == a[i]) {
                temp.push_back(i);
            }
        }
        int n = temp.size();
        int r = rand()%n;
        return temp[r];
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * int param_1 = obj->pick(target);
 */

Java code for Random Pick Index

class Solution {
    private int[] a;
    private Random rand;
    public Solution(int[] nums) {
        a=nums;
        rand = new Random();
    }
    
    public int pick(int target) {
        List<Integer> indices = new ArrayList<>();
        for(int i=0; i<a.length; i++) {
            if(a[i] == target) {
                indices.add(i);
            }
        }
        int n = indices.size();
        int res = indices.get(rand.nextInt(n));
        return res;
    }
}

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

Complexity Analysis for Random Pick Index LeetCode Solution

  • Time Complexity: O(N)
    • N represents the size of nums, In pick(), the loop iterates over all the values in a
  • Space Complexity: O(N)
    • space required by indices or temp array in pick method

Reference: https://docs.oracle.com/javase/8/docs/api/java/util/Random.html

Translate »