Java O(1) average solution using two hashmaps


  • 0
    B
    public class RandomizedCollection {
        HashMap<Integer, ArrayList<Integer>> mapwitharray = new HashMap<>();
        HashMap<Integer, HashMap<Integer, Integer>> mapwithindexmap = new HashMap<>();
        ArrayList<Integer> list = new ArrayList<>();
        Random r = new Random();
    
        public RandomizedCollection() {
        }
        
        public boolean insert(int val) {
            ArrayList<Integer> indexlist = mapwitharray.get(val);
            HashMap<Integer, Integer> map = mapwithindexmap.get(val);
            boolean result = false;
            
            if(indexlist == null){
                result = true;
                indexlist = new ArrayList<>();
                map = new HashMap<>();
                mapwitharray.put(val, indexlist);
                mapwithindexmap.put(val, map);
            }
            
            indexlist.add(list.size());
            map.put(list.size(), indexlist.size()-1);
            list.add(val);
            return result;
        }
        
        public boolean remove(int val) {
            if(!mapwitharray.containsKey(val)) return false;
            
            ArrayList<Integer> indexlist = mapwitharray.get(val);
            HashMap<Integer, Integer> map = mapwithindexmap.get(val);
            int index = indexlist.get(indexlist.size()-1);
    
            indexlist.remove(indexlist.size()-1);
            map.remove(index);
            
            list.set(index, list.get(list.size() -1));
    
            if(index+1 != list.size()){
                int lastval = list.get(list.size() -1);
                ArrayList<Integer> lastlist = mapwitharray.get(lastval);
                HashMap<Integer, Integer> lastmap = mapwithindexmap.get(lastval);
                int lastindex = lastmap.get(list.size()-1);
                lastlist.set(lastindex, index);
                lastmap.remove(list.size() -1);
                lastmap.put(index, lastindex);            
            }
            
            list.remove(list.size()-1);
            if(indexlist.size() == 0){
                mapwitharray.remove(val);
                mapwithindexmap.remove(val);
            }
            
            return true;
        }
        
        public int getRandom() {
            int index = r.nextInt(list.size());
            return list.get(index);
        }
    }
    

Log in to reply
 

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