package com.fishercoder.solutions;

import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.Random;

public class _380 {

    public static class Solution1 {
        /**
         * credit: https://leetcode.com/problems/insert-delete-getrandom-o1/discuss/85401/Java-solution-using-a-HashMap-and-an-ArrayList-along-with-a-follow-up.-(131-ms)
         */
        public static class RandomizedSet {
            Map<Integer, Integer> map;
            List<Integer> list;
            Random random;

            public RandomizedSet() {
                map = new HashMap<>();
                random = new Random();
                list = new ArrayList<>();
            }

            public boolean insert(int val) {
                if (map.containsKey(val)) {
                    return false;
                }
                map.put(val, list.size());
                list.add(list.size(), val);
                return true;
            }

            public boolean remove(int val) {
                if (!map.containsKey(val)) {
                    return false;
                } else {
                    int lastElement = list.get(list.size() - 1);
                    int index = map.get(val);
                    list.set(index, lastElement);
                    map.put(lastElement, index);
                    list.remove(list.size() - 1);
                    map.remove(val);
                    return true;
                }
            }

            public int getRandom() {
                return list.get(random.nextInt(list.size()));
            }
        }
    }

}

@@ -1165,16 +1165,243 @@
     int 
+removeIndex = map.get(val);%0A                    if (removeIndex != list.size() - 1) %7B//if it's not the last element, then we need to swap it with the last element so that this operation is also O(1)%0A                        int 
 lastElem
@@ -1441,50 +1441,8 @@
     
-                int index = map.get(val);%0A
     
@@ -1466,17 +1466,23 @@
 ist.set(
-i
+removeI
 ndex, la
@@ -1505,32 +1505,36 @@
                 
+  
+  
 map.put(lastElem
@@ -1538,17 +1538,23 @@
 lement, 
-i
+removeI
 ndex);%0A 
@@ -1576,35 +1576,44 @@
     
-list.remove(list.size() - 1
+%7D%0A                    map.remove(val
 );%0A 
@@ -1627,35 +1627,36 @@
             
-map
+list
 .remove(
 val);%0A      
@@ -1635,35 +1635,47 @@
     list.remove(
-val
+list.size() - 1
 );%0A             

fix 380