Java clean and readable solution with explainations (O(1), 148ms)


  • 0
    B

    Hi,

    The principle here is to have a list of all the integers contained in the collection. A map keeps a set of indexes for each value in the collection since a value can appear multiple times.

    insert is pretty straightforward. We just add the value at the end of the list (O(1) on average) and we add the index to the map (also O(1) on average).

    getRandom is also quite simple. We just uniformly select a random index and return the value at this index. If a value appears multiple times in the collection, its probability of being returned is proportional to its number of occurrences, just as expected.

    remove is a bit more complicated. We cannot remove a value in the middle of the list because that would take O(n). So, instead of removing it, we're gonna replace it with the last value of the list and then we're gonna remove the last value. We also need to update the indexes of the removed value and the last value of the list.

    Replacing a value inside the list take O(1) on average because I'm using an ArrayList (a LinkedList wouldn't work). Removing the last element and updating the two indexes also takes O(1) on average.

    In order to keep the code clean, I'm using meaningful variable names and local variables to avoid redundant code.

    I'm also using ThreadLocalRandom to generate random numbers. It's much cleaner than using Math.random. Using a Random variable would be ok too.

    Here's the code. Enjoy! :)

    import java.util.concurrent.*;
    
    public class RandomizedCollection {
        
        private List<Integer> numbers;
        
        private Map<Integer, Set<Integer>> indexes;
        
        /** Initialize your data structure here. */
        public RandomizedCollection() {
            numbers = new ArrayList<>();
            indexes = new HashMap<>();
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            boolean absent = !indexes.containsKey(val);
            if (absent) {
                indexes.put(val, new HashSet<>());
            }
            indexes.get(val).add(numbers.size());
            numbers.add(val);
            return absent;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            if (!indexes.containsKey(val)) {
                return false;
            }
            
            // Removes val index from indexes and put it in the index variable
            Set<Integer> valIndexes = indexes.get(val);
            Iterator<Integer> it = valIndexes.iterator();
            int index = it.next();
            it.remove();
            if (valIndexes.isEmpty()) {
                indexes.remove(val);
            }
            
            int lastIndex = numbers.size() - 1;
            // Swap the removed value with the last one (if needed) and remove it
            if (lastIndex != index) {
                int lastVal = numbers.get(lastIndex);
                // Move last value to index
                numbers.set(index, lastVal);
                // Update last value index
                Set<Integer> lastIndexes = indexes.get(lastVal);
                lastIndexes.remove(lastIndex);
                lastIndexes.add(index);
            }
            numbers.remove(lastIndex);
            return true;
        }
        
        /** Get a random element from the collection. */
        public int getRandom() {
            return numbers.get(ThreadLocalRandom.current().nextInt(numbers.size()));
        }
    }
    

Log in to reply
 

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