Q54 Insert Delete GetRandom O(1) - LeetCode

PHOTO

Tue Jan 31 2023 10:14:17 GMT+0000 (UTC)

Saved by @Ayush_dabas07

class RandomizedSet {
    
    HashMap<Integer,Integer>map;    //to store val , index
    ArrayList<Integer> arr; //to store values and getting random in O(1)
    
    Random r;

    public RandomizedSet() {
     this.map = new HashMap<>();
     this.arr = new ArrayList<>();
     

     this.r = new Random();
        
    }
    
    public boolean insert(int val) {
        
        if(this.map.containsKey(val)) return false;  //if already present
        
        this.map.put(val,arr.size());
        this.arr.add(val);
        

        return true;
    }
    
    public boolean remove(int val) {
        if(this.map.containsKey(val)==false) return false;
        
        //removing from AL in o(1)
        int idx = this.map.get(val);         //get index in O(1)
        this.map.remove(val);

        //if element to be removed is already at arr.size()-1 index
        if(arr.size()-1 == idx)
        arr.remove(arr.size()-1);

        else{
        //swap with arr.size()-1 element as traversing and getting the element will make it O(n)
        int current_value = this.arr.get(arr.size()-1);
        Collections.swap(this.arr, idx, arr.size()-1);
        
        //now remove latest element which is O(1) and also update index of that element
        // in HM
        this.arr.remove(arr.size()-1);
        this.map.put(current_value,idx); //update swapped value index;

        }

        return true;

    }
    
    public int getRandom() {
        //get random index from arraylist
        
        //this will give a random number from 0 to list.size()-1
        int idx = r.nextInt(arr.size());  

        int val = arr.get(idx);

        return val;
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

https://leetcode.com/problems/insert-delete-getrandom-o1/

Save snippets that work from anywhere online with our extensions

Available in the Chrome Web Store

Get Firefox Add-on

Get VS Code extension

Comments

More like this

HashMap And Heaps

@Ayush_dabas07

Q64 Snapshot Array - LeetCode Q63 Reorganize String - LeetCode Q62 Tricky Sorting Cost | Practice | GeeksforGeeks Q62 Minimum Cost To Connect Sticks Q60 PepCoding | Longest Substring With At Most Two Distinct Characters Q59 PepCoding | Line Reflection Q58 Pairs of Non Coinciding Points | Practice | GeeksforGeeks Q57 Avoid Flood in The City - LeetCode Q56 Random Pick with Blacklist - LeetCode Q55 Insert Delete GetRandom O(1) - Duplicates allowed - LeetCode Q55 Insert Delete GetRandom O(1) - Duplicates allowed - LeetCode Q54 Insert Delete GetRandom O(1) - LeetCode Q53 The Skyline Problem - LeetCode Q52 Encode and Decode TinyURL - LeetCode Q51 Maximum Frequency Stack - LeetCode Q50 Brick Wall - LeetCode Q50 Brick Wall - LeetCode Q49 X of a Kind in a Deck of Cards - LeetCode Q48 First Unique Character in a String - LeetCode Q47 Subdomain Visit Count - LeetCode Q46 Powerful Integers - LeetCode Q45 4Sum II - LeetCode Q44 PepCoding | Quadruplet Sum QFind K Pairs with Smallest Sums - LeetCode Q43 PepCoding | Pairs With Given Sum In Two Sorted Matrices Q42 Completing tasks | Practice | GeeksforGeeks Q41 Degree of an Array - LeetCode Q-40 Can Make Arithmetic Progression From Sequence - LeetCode Q39 PepCoding | Double Pair Array Q38 Rabbits in Forest - LeetCode Q-37* Fraction to Recurring Decimal - LeetCode Q36 PepCoding | Pairs With Equal Sum Q35 PepCoding | Count Of Subarrays With Equal Number Of 0s 1s And 2s Q34 PepCoding | Longest Subarray With Equal Number Of 0s 1s And 2s Q-34PepCoding | Pairs With Equal Sum Q33 PepCoding | Count Of Subarrays With Equal Number Of Zeroes And Ones Q32 Contiguous Array - LeetCode Q31 Subarray Sums Divisible by K - LeetCode Q30 PepCoding | Longest Subarray With Sum Divisible By K Q29 Subarray Sum Equals K - LeetCode Q27 Word Pattern - LeetCode Q-26 Isomorphic Strings - LeetCode Q-25 PepCoding | Group Shifted String Q24 Group Anagrams - LeetCode Q23 Valid Anagram - LeetCode Q22 PepCoding | Find Anagram Mappings Q21 PepCoding | K Anagrams Q20 Find All Anagrams in a String - LeetCode Q-19 Binary String With Substrings Representing 1 To N - LeetCode Q-18 PepCoding | Count Of Substrings Having At Most K Unique Characters Q-17 PepCoding | Longest Substring With At Most K Unique Characters Q-16 PepCoding | Maximum Consecutive Ones - 2 Q15 PepCoding | Maximum Consecutive Ones - 1 Q-14 PepCoding | Equivalent Subarrays Q13 PepCoding | Count Of Substrings With Exactly K Unique Characters Q-12 PepCoding | Longest Substring With Exactly K Unique Characters Q-11 PepCoding | Count Of Substrings Having All Unique Characters Q-10 PepCoding | Longest Substring With Non Repeating Characters Q-9 PepCoding | Smallest Substring Of A String Containing All Unique Characters Of Itself Q8 PepCoding | Smallest Substring Of A String Containing All Characters Of Another String | leetcode76 Q-7 PepCoding | Largest Subarray With Contiguous Elements Q-6 PepCoding | Count Of All Subarrays With Zero Sum Q5 PepCoding | Largest Subarray With Zero Sum Q4 PepCoding | Count Distinct Elements In Every Window Of Size K Q-3 PepCoding | Check If An Array Can Be Divided Into Pairs Whose Sum Is Divisible By K Q2 PepCoding | Find Itinerary From Tickets Q1 PepCoding | Number Of Employees Under Every Manager

Browse more snippets >>