Efficient Random Index Selection for Duplicates – LeetCode 398 Explained

Problem Description

Platform: LeetCode Problem #: 398

Given an integer array that may contain duplicates, implement a function that returns a random index of a given target number. The target is guaranteed to exist in the array. The array can be very large, so solutions using excessive extra space will not pass.

Hash Table + Preprocessing (Fixed‑length data stream)

During construction, iterate over nums and store for each value a list of its indices in a hash map.

When pick(target) is called, retrieve the list of indices for target and return a random element.

Java implementation:

class Solution {
    Random random = new Random();
    Map<Integer, List<Integer>> map = new HashMap<>();
    public Solution(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            List<Integer> list = map.getOrDefault(nums[i], new ArrayList<>());
            list.add(i);
            map.put(nums[i], list);
        }
    }
    public int pick(int target) {
        List<Integer> list = map.get(target);
        return list.get(random.nextInt(list.size()));
    }
}

C++ implementation:

class Solution {
public:
    unordered_map<int, vector<int>> map;
    Solution(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            map[nums[i]].push_back(i);
        }
    }
    int pick(int target) {
        vector<int>& list = map[target];
        return list[rand() % list.size()];
    }
};

Python implementation:

class Solution:
    def __init__(self, nums: List[int]):
        self.mapping = {}
        n = len(nums)
        for i in range(n):
            if nums[i] not in self.mapping:
                self.mapping[nums[i]] = []
            self.mapping[nums[i]].append(i)

    def pick(self, target: int) -> int:
        return random.choice(self.mapping.get(target, []))

Time complexity: O(n) for initialization, O(1) for each pick. Space complexity: O(n).

Reservoir Sampling (Variable‑length data stream) – TLE

If the array is not fully known in advance and arrives as a stream, preprocessing is infeasible. Reservoir sampling can select a random index with O(1) extra space.

During each pick, iterate over the stream, maintaining a count of matching indices and replace the current answer with probability 1/count.

Java implementation:

class Solution {
    Random random = new Random();
    int[] nums;
    public Solution(int[] _nums) {
        nums = _nums;
    }
    public int pick(int target) {
        int n = nums.length, ans = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == target) {
                cnt++;
                if (random.nextInt(cnt) == 0) ans = i;
            }
        }
        return ans;
    }
}

C++ implementation:

class Solution {
public:
    vector<int> nums;
    mt19937 random;
    Solution(vector<int>& _nums) : nums(_nums) {
        srand(time(nullptr));
        random.seed(rand());
    }
    int pick(int target) {
        int ans = -1, cnt = 0;
        for (size_t i = 0; i < nums.size(); i++) {
            if (nums[i] == target) {
                cnt++;
                if (uniform_int_distribution<>(0, cnt - 1)(random) == 0) {
                    ans = i;
                }
            }
        }
        return ans;
    }
};

Python implementation:

class Solution:
    def __init__(self, nums: List[int]):
        self.nums = nums
    def pick(self, target: int) -> int:
        ans, cnt = 0, 0
        for i in range(len(self.nums)):
            if self.nums[i] == target:
                cnt += 1
                if random.randint(0, cnt - 1) == 0:
                    ans = i
        return ans

Time complexity: O(n) per pick. Space complexity: O(1).