Java solution using a HashMap and an ArrayList along with a follow-up. (131 ms)


  • 176

    I got a similar question for my phone interview. The difference is that the duplicated number is allowed. So, think that is a follow-up of this question.
    How do you modify your code to allow duplicated number?

    public class RandomizedSet {
        ArrayList<Integer> nums;
        HashMap<Integer, Integer> locs;
        java.util.Random rand = new java.util.Random();
        /** Initialize your data structure here. */
        public RandomizedSet() {
            nums = new ArrayList<Integer>();
            locs = new HashMap<Integer, Integer>();
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            boolean contain = locs.containsKey(val);
            if ( contain ) return false;
            locs.put( val, nums.size());
            nums.add(val);
            return true;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            boolean contain = locs.containsKey(val);
            if ( ! contain ) return false;
            int loc = locs.get(val);
            if (loc < nums.size() - 1 ) { // not the last one than swap the last one with this val
                int lastone = nums.get(nums.size() - 1 );
                nums.set( loc , lastone );
                locs.put(lastone, loc);
            }
            locs.remove(val);
            nums.remove(nums.size() - 1);
            return true;
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            return nums.get( rand.nextInt(nums.size()) );
        }
    }
    

  • 0

    Easily understandable !
    Thanks


  • 0
    L

    Thanks, I came up with a similar idea except had trouble handling deleting item from list.


  • 77

    The follow-up: allowing duplications.
    For example, after insert(1), insert(1), insert(2), getRandom() should have 2/3 chance return 1 and 1/3 chance return 2.
    Then, remove(1), 1 and 2 should have an equal chance of being selected by getRandom().

    The idea is to add a set to the hashMap to remember all the locations of a duplicated number.

    public class RandomizedSet {
    	    ArrayList<Integer> nums;
    	    HashMap<Integer, Set<Integer>> locs;
    	    java.util.Random rand = new java.util.Random();
    	    /** Initialize your data structure here. */
    	    public RandomizedSet() {
    	        nums = new ArrayList<Integer>();
    	        locs = new HashMap<Integer, Set<Integer>>();
    	    }
    	    
    	    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    	    public boolean insert(int val) {
    	        boolean contain = locs.containsKey(val);
    	        if ( ! contain ) locs.put( val, new HashSet<Integer>() ); 
    	        locs.get(val).add(nums.size());        
    	        nums.add(val);
    	        return ! contain ;
    	    }
    	    
    	    /** Removes a value from the set. Returns true if the set contained the specified element. */
    	    public boolean remove(int val) {
    	        boolean contain = locs.containsKey(val);
    	        if ( ! contain ) return false;
    	        int loc = locs.get(val).iterator().next();
                    locs.get(val).remove(loc);
    	        if (loc < nums.size() - 1 ) {
    	            int lastone = nums.get(nums.size() - 1 );
    	            nums.set( loc , lastone );
    	            locs.get(lastone).remove(nums.size() - 1);
    	            locs.get(lastone).add(loc);
    	        }
    	        nums.remove(nums.size() - 1);
    	        if (locs.get(val).isEmpty()) locs.remove(val);
    	        return true;
    	    }
    	    
    	    /** Get a random element from the set. */
    	    public int getRandom() {
    	        return nums.get( rand.nextInt(nums.size()) );
    	    }
    	}
    

  • 0
    D

    @yubad2000 One question: what is the time complexity for a set to return its iterator?


  • 1

    @dachuan.huang
    According to Javadoc

    Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets).

    Therefore, we can consider replacing the HashSet with a LinkedHashSet which should have a constant time of getting the first element because the order of all elements is maintained during each operation. Here is the modification.


  • 8
    S

    Is the List.remove() a O(1) operation?


  • 8

    @SuperBrother
    It is O(1) only when removing the last element by index.
    here is the post for the explanation.

    Here is how it's implemented. elementData does a lookup on the backing array (so it can cut it loose from the array), which should be constant time (since the JVM knows the size of an object reference and the number of entries it can calculate the offset), and numMoved is 0 for this case:

    public E remove(int index) {
        rangeCheck(index); // throws an exception if out of bounds
    
        modCount++;        // each time a structural change happens
                           // used for ConcurrentModificationExceptions
    
        E oldValue = elementData(index);
    
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // Let gc do its work
    
        return oldValue;
    }
    

  • 0
    This post is deleted!

  • 0
    I

    @yubad2000
    "The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking)" From ArrayList. Better use 2 HashMap then.


  • 0

    @iambright
    Sure, it is a choice of using two hash tables for the solution. The java doc says "adding n elements requires O(n) time" should mean adding n elements at the same time, such as call addAll(), or using ArrayList(Collection<? extends E> c) for construction. Or, when calling add(int index, E element), it is amortized constant time since if shift any subsequent elements to the right. However, calling add() just add one element at the end of this list is O(1).

    Same as the remove(int index) call, it removes the element at the specified position in this list and shifts any subsequent elements to the left (subtracts one from their indices). When removing the last element at the end of this list, it is O(1).


  • 0
    I

    @yubad2000 "amortized constant time", means add() n times (n is big) costs linear time. If it exceeds its current allocated memory it has to do a realloc and copy, that last add() alone will cost linear time.


  • 0

    @iambright
    I totally agree with what you said. The same topic on O(1) time has been discussed in this post. Actually, even hash table is not "truly" O(1) either.


  • 0
    I

    @yubad2000 Sure hash map is not truly constant. But for a question asking for constant time, you don't want to give a solution that after 32 insertions for sure a linear time performance is waiting ahead of you. It seems HashMap also has the same issue, O(1) is too ideal.


  • 0
    M

    Wow! Thank you for sharing this!
    You know what, I was stuck at the remove part. I did not get your smart method of swapping the last element with the deleted element. This is very enlightening!


  • 5

    Upvote! It is hard to find this swap solution for remove.


  • -1
    H

    @yubad2000
    I used a ArrayList instead of HashSet to store the positions of the duplicates, and each remove operation I remove the last occurrence of the duplicates. But it passed only 27/28 test cases. Here is the code:

    public class RandomizedCollection {
    HashMap<Integer, List<Integer>> map=new HashMap<>();
    List<Integer> nums=new ArrayList<>();

    /** Initialize your data structure here. */
    public RandomizedCollection() {
        
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        boolean contains=false;
        if (!map.containsKey(val)) contains=true;
        if (contains==false) map.get(val).add(nums.size());
        else{
            List<Integer> indexs=new ArrayList<>();
            indexs.add(nums.size());
            map.put(val, indexs);
        }
        nums.add(val);
        return contains;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        boolean contains=true;
        if (!map.containsKey(val)) return false;
        List<Integer> indexs=map.get(val);
        int ind=indexs.get(indexs.size()-1);
        if (ind<nums.size()-1){
            int last=nums.get(nums.size()-1);
            nums.set(ind, last);
            List<Integer> temp=map.get(last);
            temp.set(temp.size()-1, ind);
            map.put(last, temp);
        }
        nums.remove(nums.size()-1);
        indexs.remove(indexs.size()-1);
        if (indexs.isEmpty()) map.remove(val);
        else map.put(val, indexs);
        return true;
        
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        return nums.get((int)(Math.random()*nums.size()));
    

    }

    And below is the failed test case:
    ["RandomizedCollection","insert","insert","insert","insert","insert","insert","remove","remove","remove","remove","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom"]
    [[],[10],[10],[20],[20],[30],[30],[10],[10],[30],[30],[],[],[],[],[],[],[],[],[],[]]

    Could you help me with this code? Thanks!

    }


  • 0

    @hezhifeng check the post here.


  • 0
    H

    @yubad2000

    Thanks! Very clear explanation!


  • 0
    V
    This post is deleted!

Log in to reply
 

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