O(n) to pre-process and O(1) to pick

  • 0
    Random random = new Random();
    Map<Integer, List<Integer>> map = new HashMap<>();
    public Solution(int[] nums) {
        for (int i = 0; i < nums.length; i++)
            map.computeIfAbsent(nums[i], k -> new ArrayList<>(4)).add(i);
    public int pick(int target) {
        List<Integer> integers = map.get(target);
        return integers.get(random.nextInt(integers.size()));

  • 0

    @snap_dragon This will get following error:
    Submission Result: Memory Limit Exceeded More Details

    Last executed input:

  • 0

    @zsll I was waiting for OJ to add an input to fail my code but surprisingly I tried again and got accepted.

    See my last accepted submissions https://leetcode.com/snap_dragon/

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.