Java HaspMap, LinkedHashSet, ArrayList (155 ms)


  • 27

    See my previous post here.
    I modified the code by replacing HashSet with LinkedHashSet because the set.iterator() might be costly when a number has too many duplicates. Using LinkedHashSet can be considered as O(1) if we only get the first element to remove.

    public class RandomizedCollection {
        ArrayList<Integer> nums;
    	HashMap<Integer, Set<Integer>> locs;
    	java.util.Random rand = new java.util.Random();
        /** Initialize your data structure here. */
        public RandomizedCollection() {
            nums = new ArrayList<Integer>();
    	    locs = new HashMap<Integer, Set<Integer>>();
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            boolean contain = locs.containsKey(val);
    	    if ( ! contain ) locs.put( val, new LinkedHashSet<Integer>() ); 
    	    locs.get(val).add(nums.size());        
    	    nums.add(val);
    	    return ! contain ;
        }
        
        /** Removes a value from the collection. Returns true if the collection 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 collection. */
        public int getRandom() {
            return nums.get( rand.nextInt(nums.size()) );
        }
    }
    

  • 0
    Z
    This post is deleted!

  • 0

    @yubad2000 Just FYI, your solution fails the recently added test cases, so you might want to take another look at it.


  • -1

    update: no longer AC !!!
    Another AC solution using ArrayList

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

  • 0

    @1337c0d3r
    Thanks, I fixed it.


  • 1
    R

    What is the benefit of using LinkedHashSet over Queue?


  • 1

    @rgc588
    Removing or getting one certain element from a set is O(1), while removing and getting a certain element from a queue is not.


  • 0
    R

    Why do you need to remove a certain element? Can you just remove the last of queue?


  • 1

    @rgc588
    Yes, I agree in this case. So, please see my second solution for my implementation using List instead of Queue.
    update
    This solution is no longer valid, see the later replies for counterexamples.


  • 0
    R
    This post is deleted!

  • 1
    R

    @yubad2000 said in Java HaspMap, LinkedHashSet, ArrayList (155 ms):

    locs.get(lastone).remove( locs.get(lastone).size() - 1);

    locs.get(lastone).remove( locs.get(lastone).size() - 1); looks incorrect to me. For example, given sequence [7,2,5,3,5,6,5], locs[5] = [2,4,6]. After remove(2), sequence becomes [7,5,5,3,5,6] with lots[5] = [2,4,1]. Then we remove 6. Then let's try to remove 7, and the above code will try to remove 1 from [2,4,1]. In contrast, 4 should be removed from [2,4,1], which results in [5,5,5,3] with locs[5] = [2,1,0].

    In conclusion, locs.get(lastone).remove( nums.size() - 1); is correct. Unfortunately, the complexity is not O(1).
    Correction: LinkedHashSet.remove() is O(1) on average.


  • 0

    @richdalgo Check the official Javadoc of LinkedHashSet:

    Like HashSet, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets.

    So, why do you think that it is not O(1)?


  • 0
    R

    @yubad2000 Sorry, that statement was a mistake. Could you clarify why removing the last from set is correct? Removing the index "nums.size() - " looks more reasonable. I admit removing the last from set works in my manual tests. Besides, why set.iterator() is expensive for large set? Thanks!


  • 0

    @richdalgo

    update: This is a False statement, please see the later replies for counterexamples.

    Removing the last element works because we alway swap the last index with the removed one.
    i.e. we have [10,10,20,20,10] initially. The hash table should look like,
    (10 [0,1,4]) ] and (20, [2,3] ) since we alway place the last index at the tail of the index list.
    When remove(2) is called, we can either remove index 2 or 3, does not matter.
    We know that 10 is at the end of the array, so we find all the indexes of where all the 10s are located.
    Since 10 is the latest added element, the index 4 is guaranteed to be the last index we want to remove.

    The following is still a True statement:
    For the reason why set.iterator() is expensive, please refer to HashSet 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).


  • 8
    I

    @yubad2000 said in Java HaspMap, LinkedHashSet, ArrayList (155 ms):

    locs.get(lastone).remove( locs.get(lastone).size() - 1);

    Removing the last element is incorrect and that's the very reason why Runtime Error occurs removing this line:

    if (loc < nums.size() - 1 )

    Suppose the initial sequence is [10, 10, 20, 20, 30, 30], with loc[30]=[4, 5]. Then we remove 10 twice. Here is what happens to the sequence: [10, 10, 20, 20, 30, 30] -> [10, 30, 20, 20, 30] -> [30, 30, 20, 20], and to loc[30]: [4, 5] -> [4, 1] -> [4, 0]. This is not true. We should remove 4 instead of the last element 1 in loc[30], when remove the second 10. And loc[30] should be [0, 1] at last.

    Let's consider this case:

    ["RandomizedCollection","insert","insert","insert","insert","insert","insert","remove","remove","remove","remove"]
    [[],[10],[10],[20],[20],[30],[30],[10],[10],[30],[30]]

    Here is the outcome, with the line "if (loc < nums.size() - 1 )" removed:

    Line 27: java.lang.IndexOutOfBoundsException: Index: 4, Size: 3

    Note that index 4 is exactly the first element of loc[30]=[4, 0]. In this case, we removes the number 30 twice. First, remove the 30 at index 0, all is well. Second, at index 4, however, resulting in IndexOutOfBoundsException.

    Maybe we can find out the the element equals to nums.size()-1 in loc[30] with ArrayList.indexOf(), not necessarily the last one, and remove it. Namely,

    //locs.get(lastone).remove( locs.get(lastone).size() - 1);
    locs.get(lastone).remove( locs.get(lastone).indexOf(nums.size() - 1) );

    Unfortunately, ArrayList.indexOf() is not O(1) on average. If you have new idea, let's have futher disscusion :)


  • 0

    @ivan.chan Good counterexample, even the OJ does not catch the issue and the solution got AC. In that case, my first solution using LinkedHashSet instead of List is one choice of removing the last index with avg O(1) time.


  • 0

    @yubad2000 said in Java HaspMap, LinkedHashSet, ArrayList (155 ms):

    even the OJ does not catch the issue and the solution got AC

    Which solution is it? I've just tested your solution with the following line removed:

    if (loc < nums.size() - 1 )

    And it gets Runtime Error as intended.


  • 1
    I

    @1337c0d3r It doesn't need to go into the following block when remove the last element of nums. Otherwise, it gets Runtime Error.

    {
    int lastone = nums.get(nums.size() - 1);
    nums.set( loc , lastone );
    locs.get(lastone).remove( locs.get(lastone).size() - 1);
    locs.get(lastone).add(loc);
    }

    In this case, "if (loc < nums.size() - 1)" should be kept. Or more precisely, use "if (loc != nums.size() - 1)". Because "if (loc < nums.size() - 1)" can conceal the IndexOutOfBoundsException bug as is explained above.

    But it seems that the OJ fails to check the probability of each element being returned. I've tried to submit the original version of AC solution, with line "if (loc < nums.size() - 1 )" and line "locs.get(lastone).remove( locs.get(lastone).size() - 1)" retained. As is explained above, removing the last element is incorrect. Theoretically, this solution doesn't return elements with proper probilities. However, the submission is accepted. It's confusing. Maybe more analysis is needed to find out the reason.


  • 0

    @1337c0d3r
    I meant even without removing

    if (loc < nums.size() - 1 )

    the solution using HashMap<Integer, List<Integer>> is wrong.
    Here is the test case

    ["RandomizedCollection","insert","insert","insert","insert","insert","insert","remove","remove","remove","insert","insert","insert", "remove","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom"]
    [[],[10],[10],[20],[20],[30],[30],[10],[10],[30],[11],[12],[13],[30],[],[],[],[],[],[]]
    

    The output was:

    [null,true,false,true,false,true,false,true,true,true,true,true,true,true,20,20,20,11,30,20]
    

    The number [30] should have been removed from the list, but the getRandom() still return [30].
    Because the program removed [12] instead of [30] so that getRandom() will not return [12] in this case.
    However, OJ accepted this solution.


  • 0
    I

    @1337c0d3r The following solution, which in fact doesn't return elements with proper probilities, is, however, accepted by the system.

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

    Given the following 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],[],[],[],[],[],[],[],[],[],[]]

    And the outcome is:

    [null,true,false,true,false,true,false,true,true,true,true,20,20,30,30,30,30,30,20,30,20]

    But the expected answer given by the system is:

    [null,true,false,true,false,true,false,true,true,true,true,20,20,20,20,20,20,20,20,20,20]

    There is no number 30 in the collection at all, but this solution still return 30 with probability 50%, as a consequence of wrongly removing the last element of locs. Obviously, the system has accepted a buggy solution. Thus, I suspect that the system fails to check the probilities of elements being returned.


Log in to reply
 

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