Scale Engineer

Random Pick Index

Med
#0385Time: 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: 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.
Patterns
MathRandomized
Algorithms
Reservoir Sampling
Data structures
Hash Table

Prompt

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 * 104
  • -231 <= nums[i] <= 231 - 1
  • target is an integer from nums.
  • At most 104 calls will be made to pick.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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.

Trade-offs

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).

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem