Random Pick Index

MEDIUM

Description

Given an integer array nums with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

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

Example 1:

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.

Constraints:

1 <= nums.length <= 2 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
target is an integer from nums.
At most 10⁴ calls will be made to pick.

Approaches

Checkout 3 different approaches to solve Random Pick Index. Click on different approaches to view the approach and algorithm in detail.

Brute Force Linear Scan

This is a straightforward brute-force approach. For every call to pick(target), we iterate through the entire input array. We collect all the indices where the element equals the target into a temporary list. Finally, we randomly select one index from this list and return it. The constructor simply stores a reference to the input array.

Algorithm

In the pick(target) method, initialize an empty list to store the indices of the target element.
Iterate through the entire nums array from the beginning to the end.
For each element, check if it is equal to the target.
If nums[i] == target, add the current index i to the list.
After the iteration is complete, the list will contain all indices where the target appears.
Generate a random number between 0 (inclusive) and the size of the list (exclusive).
Return the element from the list at the randomly generated index.

The Solution class stores the input array. The pick method performs a linear scan of this array. It uses an auxiliary ArrayList to keep track of all indices i where nums[i] matches the target. Once the entire array has been scanned, it means we have found all possible indices. Then, a random index is chosen from this list of indices. Since every valid index is in the list, and we pick a random element from the list, each index has an equal probability of being chosen.

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Solution {
    private int[] nums;
    private Random rand;

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

Complexity Analysis

Time Complexity: O(N) for each call to `pick(target)`, where N is the number of elements in the array, because we need to scan the entire array. The constructor takes O(1) time.Space Complexity: O(K) for the `pick` method, where K is the number of occurrences of the `target`. This is for the list used to store indices. In the worst-case scenario where all elements are the target, the space complexity becomes O(N). The overall space for the class is O(N) to store the array.

Pros and Cons

Pros:

Simple to understand and implement.
The constructor is very fast (O(1)) and uses minimal memory beyond storing the array itself.

Cons:

The pick operation has a time complexity of O(N), which is inefficient if it's called many times.
The space complexity for pick is O(K), where K is the number of occurrences of the target. In the worst case, this can be O(N).

Code Solutions

Checking out 3 solutions in different languages for Random Pick Index. Click on different languages to view the code.

class Solution { private int [] nums ; private Random random = new Random (); public Solution ( int [] nums ) { this . nums = nums ; } public int pick ( int target ) { int n = 0 , ans = 0 ; for ( int i = 0 ; i < nums . length ; ++ i ) { if ( nums [ i ] == target ) { ++ n ; int x = 1 + random . nextInt ( n ); if ( x == n ) { ans = i ; } } } return ans ; } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(nums); * int param_1 = obj.pick(target); */

Video Solution

Watch the video walkthrough for Random Pick Index

Algorithms:

Reservoir Sampling

Patterns:

MathRandomized

Data Structures:

Hash Table