# 380. Insert Delete GetRandom O(1)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FJPP2BMfq1axhyUUtbZje%2Fimage.png?alt=media\&token=0e24a8cb-5c0d-4a3d-ab41-af6aa8eec96a)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FlKP7FlIhUZVPUvDhS51m%2Fimage.png?alt=media\&token=aa94bf7e-b938-4a4d-911c-f36919601e7e)

time: all O(1)

space: O(1\~n)

```java
class RandomizedSet {

    private List<Integer> nums;
    private Map<Integer, Integer> numToIndex; // map<num, num's index>
    private Random rand;
    
    public RandomizedSet() {
        nums = new ArrayList<>();
        numToIndex = new HashMap<>();
        rand = new Random();
    }
    
    public boolean insert(int val) {
        //if insert ok return true, or false
        if (numToIndex.containsKey(val)) {
            return false;
        }
        numToIndex.put(val, nums.size()); // 
        nums.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        //if remove ok return true, or false
        if (!numToIndex.containsKey(val)) {
            return false;
        }
        // how to not shift each index? 
        // if not delete last num, replace delete num's position by last num, then delete last num
        // deleteNum,xxxxx  lastNum
        int deleteNumIndex = numToIndex.get(val);
        int lastNum = nums.get(nums.size()-1);
        if (deleteNumIndex != nums.size()-1) {
            nums.set(deleteNumIndex, lastNum);
            numToIndex.put(lastNum,deleteNumIndex);
        }
        nums.remove(nums.size()-1);
        numToIndex.remove(val);
        return true;
    }
    
    public int getRandom() {
        // guaranteed that at least one element exists when this method is called
        return nums.get(rand.nextInt(nums.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();
 */j
```
