Insert Delete GetRandom O(1)

Master this topic with zero to advance depth.

Insert Delete GetRandom O(1)

To achieve $O(1)$ average time for all operations, we combine a HashMap and an ArrayList. The ArrayList stores the values for $O(1)$ random access, while the HashMap stores value-to-index mappings for $O(1)$ lookups and deletions. Deletion is optimized by swapping the target element with the last element in the list.

Implement the RandomizedSet class: bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise. bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise. int getRandom() Returns a random element from the current set of elements. Each element must have the same probability of being returned. All operations must be O(1) average time complexity.

Visual Representation

Insert 10: Array=[10], Map={10: 0}
Insert 20: Array=[10, 20], Map={10: 0, 20: 1}
Remove 10:
1. Swap 10 with last (20): Array=[20, 10]
2. Update Map: {20: 0}
3. Pop last: Array=[20]

Medium

Examples

Input: ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output: [null, true, false, true, 2, true, false, 2]
RandomizedSet randomizedSet = new RandomizedSet(); randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomizedSet.remove(2); // Returns false as 2 does not exist in the set. randomizedSet.insert(2); // Inserts 2 to the set, returns true. randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly. randomizedSet.remove(1); // Removes 1 from the set, returns true. randomizedSet.insert(2); // 2 was already in the set, so return false. randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Approach 1

Level I: Brute Force (ArrayList only)

Intuition

Use a simple dynamic array (ArrayList/vector) to store elements. For insert, we first check if the element exists by scanning the entire list, which takes O(N). For remove, we search for the element (O(N)) and then shift remaining elements (O(N)). For getRandom, we pick a random index in O(1). This approach fails the O(1) requirement for insert and remove.

⏱ O(N) for insert/remove, O(1) for getRandom💾 O(N) to store elements.

Detailed Dry Run

Action	List	Result
insert(1)	[1]	true
insert(1)	[1]	false (contains)
getRandom	[1]	1

java

import java.util.*;

public class RandomizedSet {
    private List<Integer> list;
    private Random random;
    public RandomizedSet() {
        list = new ArrayList<>();
        random = new Random();
    }
    public boolean insert(int val) {
        if (list.contains(val)) return false;
        list.add(val); return true;
    }
    public boolean remove(int val) {
        return list.remove(Integer.valueOf(val));
    }
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
    public static void main(String[] args) {
        RandomizedSet rs = new RandomizedSet();
        System.out.println(rs.insert(1)); // true
        System.out.println(rs.remove(2)); // false
        System.out.println(rs.insert(2)); // true
        System.out.println(rs.getRandom()); // 1 or 2
    }
}

Approach 2

Level II: Better Solution (HashSet)

Intuition

A HashSet allows insert and remove operations in O(1) average time. However, sets do not support efficient random access by index. To implement getRandom, we must either iterate through the set or convert it to an array/list, both of which take O(N) time. This approach optimizes insert/remove but at the cost of a slow getRandom.

⏱ O(1) for insert/remove, O(N) for getRandom💾 O(N) to store unique elements.

Detailed Dry Run

Action	Set	Result
insert(1)	{1}	true
getRandom	list({1})	1 (Slow conversion)

java

import java.util.*;

public class RandomizedSet {
    private Set<Integer> set;
    private Random random;
    public RandomizedSet() {
        set = new HashSet<>();
        random = new Random();
    }
    public boolean insert(int val) { return set.add(val); }
    public boolean remove(int val) { return set.remove(val); }
    public int getRandom() {
        Integer[] arr = set.toArray(new Integer[0]); // O(N)
        return arr[random.nextInt(arr.length)];
    }
    public static void main(String[] args) {
        RandomizedSet rs = new RandomizedSet();
        System.out.println(rs.insert(1)); // true
        System.out.println(rs.getRandom()); // 1
    }
}

Approach 3

Level III: Optimal Solution (HashMap + Array)

Intuition

To achieve O(1) for all operations, we combine a HashMap and a dynamic array (List). The List stores elements for O(1) random access, and the HashMap stores value -> index mapping for O(1) lookup. The key trick is in remove: instead of shifting elements (O(N)), we swap the target element with the last element of the list, update its index in the map, and pop the last element in O(1).

⏱ O(1) average for all operations.💾 O(N) to store elements and their index mappings.

Detailed Dry Run

O(1) Removal Visualization

List: [10, 20, 30, 40]  Map: {10:0, 20:1, 30:2, 40:3}
Remove 20:
1. Find index of 20 (index = 1)
2. Get last element (40)
3. Set List[1] = 40, Update Map {40:1}
4. Pop last element from List, delete 20 from Map
Result: [10, 40, 30]  Map: {10:0, 40:1, 30:2}

java

import java.util.*;

public class RandomizedSet {
    private Map<Integer, Integer> map; // value -> index
    private List<Integer> list; // values
    private Random random;
    
    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
        random = new Random();
    }
    
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        map.put(val, list.size());
        list.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int index = map.get(val);
        int lastElement = list.get(list.size() - 1);
        
        // Swap with last element
        list.set(index, lastElement);
        map.put(lastElement, index);
        
        // Remove last element
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }
    
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }

    public static void main(String[] args) {
        RandomizedSet rs = new RandomizedSet();
        System.out.println(rs.insert(10)); // true
        System.out.println(rs.insert(20)); // true
        System.out.println(rs.remove(10)); // true
        System.out.println(rs.getRandom()); // 20
    }
}

← Previous QuestionFirst Missing Positive

Next Question →Count of Smaller Numbers After Self

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.