Simple idea of using HashMap + ArrayList

  • 0
    public class RandomizedSet {
        Map<Integer, Integer> valToIdxMap = new HashMap<>();
        List<Integer> array = new ArrayList<>();
        Random rand = new Random();
        public boolean insert(int val) {
                return false;
            valToIdxMap.put(val, array.size()-1);
            return true;
        public boolean remove(int val) {
                return false;
            int idx = valToIdxMap.get(val);
            if(idx<array.size()-1) {
                array.set(idx, array.get(array.size()-1)); // swap
                valToIdxMap.put(array.get(idx), idx); // update swapped
            array.remove(array.size()-1); // list delete last idx is O(1)
            return true;
        public int getRandom() {
            return array.get(rand.nextInt(array.size()));

Log in to reply

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