_380. Insert Delete GetRandom O(1).md

380. Insert Delete GetRandom O(1)

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 06, 2024

Last updated : July 06, 2024

---

Related Topics : Array, Hash Table, Math, Design, Randomized

Acceptance Rate : 54.79 %

---

Solutions

• m380.java

Java

m380.java

class RandomizedSet {
    private ArrayList<Integer> vals;
    private HashMap<Integer, Integer> indices;
    public RandomizedSet() {
        this.vals = new ArrayList<>();
        this.indices = new HashMap<>();
        
    }
    
    public boolean insert(int val) {
        if (this.indices.containsKey(val)) {
            return false;
        }
        this.indices.put(val, this.vals.size());
        this.vals.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if (!this.indices.containsKey(val)) {
            return false;
        }

        int indx = this.indices.remove(val);
        if (indx == vals.size() - 1) {
            this.vals.removeLast();
        } else {
            int lastVal = this.vals.removeLast();
            this.vals.set(indx, lastVal);
            this.indices.put(lastVal, indx);
        }
        return true;
    }
    
    public int getRandom() {
        return this.vals.get((int) (Math.random() * this.vals.size()));
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */