Problem Random Pick Index

  • 0

    Dear all,
    I am curious about the solution of the problem Random Pick Index: I have used a HashMap of ArrayLists to save the position of each character in an array (the keys are the elements of the array, the values the list of possible positions). My submission was not accepted because of "Time Limit Error", and when I asked the admins I received the answer "Your solution is a brute force solution, it will not be accepted by the judge.".

    Is there any way to beat the O(n) preprocessing time and the O(1) query time? I really cannot find one. For more info, the code follows!

    In any case, I thank the admins for this great website, and the great weekly contests, that are really funny!

    PS: surprisingly, the same solution was accepted when I re-tried it more than one hour later!

    public HashMap<Integer, ArrayList<Integer>> hash = new HashMap<Integer, ArrayList<Integer>>();
    public Solution(int nums[]) {
    for (int i = 0; i < nums.length; i++) {
    if (!hash.containsKey(nums[i])) {
    hash.put(nums[i], new ArrayList<Integer>());
    public int pick(int target) {
    ArrayList<Integer> cur = hash.get(target);
    return cur.get((int) (Math.random() * cur.size()));

Log in to reply

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