Simple intuitive java O(1) solution,using hashmap and arraylist, beats 91%


  • 2
    C

    This question actually tests you how to solve the problem that ArrayList.remove() takes O(n).
    So the answer is that remove(m) where m is the index of the last element, takes O(1).

    ArrayList<Integer> nums = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>(); //stores indices
        /** Initialize your data structure here. */
        public RandomizedSet() {
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            if(!map.containsKey(val)){
                nums.add(val);
                map.put(val, nums.size()-1);
                return true;
            }
            return false;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if(map.containsKey(val)){
                int last = nums.get(nums.size()-1);
                int removePos = map.get(val);
                nums.set(removePos, last); //replace the removed number with the last number
                nums.remove(nums.size()-1); //always remove the last element, takes O(1)
                map.put(last, removePos); //upadate index
                map.remove(val);
                return true;
            }
            return false;
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            int index = (int)(Math.random() * nums.size());
            return nums.get(index);
        }
    

  • 0
    M

    I am not so sure about this code. My intuition is that ArrayList works with pointers behind the scene. So, it should iterate through all the pointers to actually reach the nth element. So, the time complexity might be O(n). Correct me if I am wrong.


  • 0
    C

    The part that takes O(n) is the shift process after the remove. In my code, I don't need any shift, so it should be O(1). The remove itself takes O(1) just like indexing in an array.


Log in to reply
 

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