LeetCode 381: Insert Delete GetRandom O(1) - Duplicates allowed Solution

Master LeetCode problem 381 (Insert Delete GetRandom O(1) - Duplicates allowed), a hard 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.

381. Insert Delete GetRandom O(1) - Duplicates allowed

Hard

Array Hash Table Math Design Randomized

Problem Explanation

Explanation:

To achieve constant time complexity for insert, remove, and getRandom operations, we can use a combination of HashMap and ArrayList. We will store the elements in the ArrayList to allow for random access, and use the HashMap to store the indices of each element in the ArrayList for efficient removal. When removing an element, we swap it with the last element in the ArrayList to maintain constant time complexity.

Algorithm:

Initialize a HashMap to store the mapping of elements to their indices in the ArrayList.
Initialize an ArrayList to store the elements.
For insert operation, add the element to the end of the ArrayList and update the HashMap with the new index.
For remove operation, get the index of the element to remove from the HashMap, swap it with the last element in the ArrayList, update the HashMap with the new index of the swapped element, and remove the last element.
For getRandom operation, generate a random index within the size of the ArrayList and return the element at that index.

Time Complexity:

Insert: O(1)
Remove: O(1)
GetRandom: O(1)

Space Complexity:

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

Solution Code

import java.util.*;

class RandomizedCollection {
    List<Integer> nums;
    Map<Integer, Set<Integer>> indexMap;
    Random rand;

    public RandomizedCollection() {
        nums = new ArrayList<>();
        indexMap = new HashMap<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        nums.add(val);
        indexMap.computeIfAbsent(val, k -> new HashSet<>()).add(nums.size() - 1);
        return indexMap.get(val).size() == 1;
    }

    public boolean remove(int val) {
        if (!indexMap.containsKey(val)) return false;
        int idxToRemove = indexMap.get(val).iterator().next();
        int lastElement = nums.get(nums.size() - 1);
        nums.set(idxToRemove, lastElement);
        indexMap.get(val).remove(idxToRemove);
        indexMap.get(lastElement).remove(nums.size() - 1);
        if (idxToRemove < nums.size() - 1) {
            indexMap.get(lastElement).add(idxToRemove);
        }
        if (indexMap.get(val).isEmpty()) indexMap.remove(val);
        nums.remove(nums.size() - 1);
        return true;
    }

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 381 (Insert Delete GetRandom O(1) - Duplicates allowed)?

This page provides optimized solutions for LeetCode problem 381 (Insert Delete GetRandom O(1) - Duplicates allowed) 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 381 (Insert Delete GetRandom O(1) - Duplicates allowed)?

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

Can I run code for LeetCode 381 on DevExCode?

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

Back to LeetCode Solutions