[Leetcode] Random Pick Index

Given an array of integers 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.

The array size can be very large. Solution that uses too much extra space will not pass the judge.


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

[Problem Link]

  • Create a Map for every target -> range[]. Now, given a target we can query its range in O(1) time. Note, that length of this range is simply range[1]-range[0]+1.
  • Given a range (for any target), generate a random_number between 0 to length_of_range (Java’s Random class allows us to generate a random number between 0 (inclusive) to n (exclusive)). We then simple return i + random_number.
class Solution {
    Map<Integer, int[]> rangeMap;
    Random r;
    public Solution(int[] nums) {
        r = new Random();
        rangeMap = new HashMap<Integer, int[]>();
        int i = 0;
        while ( i < nums.length ) {
            int num = nums[i];
            int j = i;
            while ( j < nums.length && nums[j] == num )
            int range[] = { i, j-1 };
            rangeMap.put(num, range);
            i = j;
    public int pick(int target) {
        int range[] = rangeMap.get(target);
        return range[0] + r.nextInt(range[1]-range[0]+1);
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);