Java solution with two HashMaps, 132 ms

• It uses two Map, and one queue. So the space is 2N. The queue is used to store the deleted indexes to make the getRandom function faster.

public class RandomizedSet {

``````private int nextInd = 0;
Queue<Integer> queue = new LinkedList<>(); // to store the deleted indexes
Map<Integer,Integer> numToInd = new HashMap<>();
Map<Integer,Integer> indToNum = new HashMap<>();
Random random = new Random();

/** Initialize your data structure here. */
public RandomizedSet() {

}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if (numToInd.containsKey(val)) return false;
int ind = 0;
if (queue.size() != 0) ind = queue.poll();
else {
ind = nextInd;
nextInd ++;
}
numToInd.put(val,ind);
indToNum.put(ind,val);
return true;
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (!numToInd.containsKey(val)) return false;
int ind = numToInd.get(val);
numToInd.remove(val);
indToNum.remove(ind);
return true;
}

/** Get a random element from the set. */
public int getRandom() {
int ind = random.nextInt(nextInd);
while (!indToNum.containsKey(ind)) ind = random.nextInt(nextInd);
return indToNum.get(ind);
}
``````

}

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