Clean O(1) Java Solution with HashMap and Set


  • 13

    The problem is a simple extension of the previous problem that did not have duplicates. Instead of storing a single index like in the previous problem, we simply store a collection of indices for all the times that a number appears in the array.

    Insert() and random() are quite straightforward. For remove(), we take advantage of the fact that adding/removing from a HashSet is O(1) average time. The logic is otherwise similar - swap the index of any one instance of the item to be removed with the item in the very last place of the array. Update the sets after doing so, and then remove the last item.

    Thanks to @yubad2000 for the wonderful idea of using a LinkedHashSet for O(1) iteration over large items. An iterator over a normal HashSet is actually O(h/n), where h is table capacity. So it is not a solution to our problem requiring O(1) time. Nor does an ArrayList instead of a HashSet work (I wasted some time on that for a while...).

    public class RandomizedCollection {
    
        ArrayList<Integer> result;
        HashMap<Integer, LinkedHashSet<Integer>> map;
        
        public RandomizedCollection() {
            result = new ArrayList<Integer>();
            map = new HashMap<Integer, LinkedHashSet<Integer>>();
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            // Add item to map if it doesn't already exist.
            boolean alreadyExists = map.containsKey(val);
            if(!alreadyExists) {
                map.put(val, new LinkedHashSet<Integer>());
            }
            map.get(val).add(result.size());
            result.add(val);
            return !alreadyExists;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            if(!map.containsKey(val)) {
                return false;
            }
            // Get arbitary index of the ArrayList that contains val
            LinkedHashSet<Integer> valSet = map.get(val);
            int indexToReplace = valSet.iterator().next();
            
            // Obtain the set of the number in the last place of the ArrayList
            int numAtLastPlace = result.get(result.size() - 1);
            LinkedHashSet<Integer> replaceWith = map.get(numAtLastPlace);
            
            // Replace val at arbitary index with very last number
            result.set(indexToReplace, numAtLastPlace);
            
            // Remove appropriate index
            valSet.remove(indexToReplace);
            
            // Don't change set if we were replacing the removed item with the same number
            if(indexToReplace != result.size() - 1) {
                replaceWith.remove(result.size() - 1);
                replaceWith.add(indexToReplace);
            }
            result.remove(result.size() - 1);
            
            // Remove map entry if set is now empty, then return
            if(valSet.isEmpty()) {
                map.remove(val);
            }
            return true;
        }
        
        /** Get a random element from the collection. */
        public int getRandom() {
            // Get linearly random item
            return result.get((int)(Math.random() * result.size()));
        }
    }
    

  • 3
    E

    your solution is false

    because when you add a new number into a linkedset, that number become the last number
    you should keep that the last number is always the max of the set.


  • 0

    @EncoreSummer

    "you should keep that the last number is always the max of the set."

    No, this is unnecessary for the code to work properly. If I had been using an ArrayList to keep track of indices, however, you would be correct.. But since I am using a hash set, I can remove the biggest item in O(1) no matter where it is.

    Edit: See later comment.


  • 1
    E

    @DeusVult your code doesn't work when submitted


  • 0

    @EncoreSummer

    I have just now fixed it.

    The error was unrelated to your comment, however. It had to do with how I was removing, then adding to the hash set. If I was attempting to insert(0) and then remove(0), the code would remove 0 from the set and then add it back in.

    Upon reading your earlier comment again, I believe that this is actually what you meant. I apologize, I thought you had meant something else entirely. Rather than your suggestion however, my fix was to only add to the set if the current index was less than the maximum index.


  • -1
    public class RandomizedCollection {
    
        /** Initialize your data structure here. */
        List<Integer> list;
        Map<Integer,LinkedHashSet<Integer>> vk;
        Random rand;
        public RandomizedCollection() {
            this.list=new ArrayList<>();
            this.vk=new HashMap<>();
            this.rand=new Random();
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            if(vk.containsKey(val)){
                vk.get(val).add(list.size());
                list.add(val);
                return false;
            }else{
                LinkedHashSet<Integer> tmp=new LinkedHashSet<>();
                tmp.add(list.size());
                vk.put(val,tmp);
                list.add(val);
                return true;
            }
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            if(vk.containsKey(val)){
                Iterator<Integer> iterator=vk.get(val).iterator();
                int index=iterator.next();
                iterator.remove();
                
                int size=list.size();
                if(index!=size-1){
                    int v=list.get(size-1);
                    list.set(index,v);
                    vk.get(v).remove(size-1);
                    vk.get(v).add(index);
                }
                list.remove(size-1);
                if(vk.get(val).size()==0) vk.remove(val);
                return true;
            }else return false;
        }
        
        /** Get a random element from the collection. */
        public int getRandom() {
            return list.get(rand.nextInt(list.size()));   
        }
    }
    
    /**
     * Your RandomizedCollection object will be instantiated and called as such:
     * RandomizedCollection obj = new RandomizedCollection();
     * boolean param_1 = obj.insert(val);
     * boolean param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();
     */
    

  • 0
    E

    @DeusVult To be honest, I have not fully understood this question yet. it seems that O(1) is difficult to reach.


  • 0

    @EncoreSummer

    The solution that I have posted should be average O(1) like the problem asks, no? The only things I do is either access elements from an array, get from a hashmap, or add/remove from set. All O(1) operations on average.


  • 5
    F

    @DeusVult

    I get the same idea as the yours. although I think that LinkedHashSet is a little tricky and Java-specific. I did not know it at the first time and incorrectly thought HashSet was ok here too.

    BTW, never use (int)(Math.random() * result.size()), use new Random().nextInt(result.size()) instead. :-)

    @EncoreSummer

    The key points:

    1. The code maintains a map: val -> set of positions in list and a list.
    2. To add new value, the code adds it to the last position (O(1)) of the list, and add the position information to the map (O(1) and O(1)).
    3. To remove the value, choose one (any) position from the set in the map, then use the last value in the list to replace the value at the specific position, then remove the last value in the list. Also update the map information.
      3.1. Why LinkedHashSet? Because it's the best data structure implementing set and allowing us to retrieve one element in O(1).
      3.2. Why do crazy stuffs in list? Because we want to make sure that the list is consecutive so that it's easier for us to get the random element.
    4. To get random value, return result.get(new Random().nextInt(result.size()));. Randomly choose one element from the list. The list should be array-like (ArrayList in Java) so that we could obtain O(1) time.

  • 0
    S
    This post is deleted!

  • 0
    M

    @EncoreSummer I can't agree more !


  • 0
    L

    Hi,Can you explain a little bit about why we need to do the work in the remove() function? Isn't it just simply remove the element from the list?


  • 0
    Z

    @liu971 Nope.If you just simply remove the element,there will be a "hole" in the arrayList.If the size of it is bigger than capacity,it needs resize,which takes a lot of time.


  • 0
    Z

    @liu971 and it's hard to iterate,cause there are some null values


Log in to reply
 

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