LeetCode 380: Insert Delete GetRandom O(1) Solution

Master LeetCode problem 380 (Insert Delete GetRandom O(1)), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

380. Insert Delete GetRandom O(1)

Medium

Array Hash Table Math Design Randomized

Problem Explanation

Explanation

To achieve O(1) average time complexity for insert, remove, and getRandom operations, we can use a HashMap to store the elements along with their indexes in an ArrayList. This way, we can perform insert and remove operations in O(1) time complexity using the HashMap. To achieve getRandom with equal probability, we can get a random index from the ArrayList and return the element at that index.

Algorithm:

Use a HashMap to store the elements and their corresponding indexes in an ArrayList.
For insert operation, check if the element is already present in the HashMap. If not, add it to the ArrayList with the next available index and update the HashMap.
For remove operation, check if the element is present in the HashMap. If it is, get its index, swap it with the last element in the ArrayList, update the indexes in the HashMap, and remove the element from the ArrayList.
For getRandom operation, generate a random index within the size of the ArrayList and return the element at that index.

Time Complexity:

Insert, Remove, and GetRandom operations all have an average time complexity of O(1).

Space Complexity:

O(n), where n is the number of elements in the RandomizedSet.

Solution Code

class RandomizedSet {
    Map<Integer, Integer> map;
    List<Integer> list;
    Random rand;

    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
        rand = 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);
        list.set(index, lastElement);
        map.put(lastElement, index);
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 380 (Insert Delete GetRandom O(1))?

This page provides optimized solutions for LeetCode problem 380 (Insert Delete GetRandom O(1)) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 380 (Insert Delete GetRandom O(1))?

The time complexity for LeetCode 380 (Insert Delete GetRandom O(1)) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 380 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 380 in Java, C++, or Python.

Back to LeetCode Solutions