The LeetCode problem Insert Delete GetRandom O(1) requires implementing a data structure that supports inserting, deleting, and retrieving random element in constant time. Here’s a detail breakdown:
Imagine you have a collection of elements, and you want to perform three key operations:
1. Add a new element.
2. Remove an existing element.
3. Get a random element, all in constant time.
Brute Force Approach
import java.util.*;
class RandomizedSet {
private List<Integer> list;
public RandomizedSet() {
list = new ArrayList<>();
}
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) val);
}
public int getRandom() {
Random random = new Random();
return list.get(random.nextInt(list.size()));
}
}• Insert: Uses ArrayList.add but checks contains, making it O(n) because of the linear search.
• Remove: Uses ArrayList.remove, which is O(n) due to the search for the element.
• GetRandom: Efficient O(1) as ArrayList.get works in constant time.
This approach is not optimal because searching for elements during insertion and deletion takes linear time.
Optimized Approach
In computer science and competitive programming, the combination of a HashMap and an ArrayList is often used for tasks that require efficient insertion, deletion, and retrieval of elements. While an ArrayList alone offers simplicity and efficiency in certain scenarios, combining it with a HashMap unlocks additional power and efficiency. Let’s dive into why this combination is so popular, particularly in coding challenges like LeetCode.
• HashMap provides quick indexing and lookup.
• ArrayList maintains the order and supports efficient random access.
• Together, they efficiently handle a mix of operations that would be slow if only one data structure was used.
import java.util.*;
class RandomizedSet {
private Map<Integer, Integer> map; // Maps value -> index in ArrayList
private List<Integer> list; // Stores the actual 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; // Value already exists
map.put(val, list.size()); // Add value and its index
list.add(val); // Add value to ArrayList
return true;
}
public boolean remove(int val) {
if (!map.containsKey(val)) return false; // Value not present
int index = map.get(val); // Get index of value
int lastVal = list.get(list.size() - 1); // Get last element in list
list.set(index, lastVal); // Swap with last element
map.put(lastVal, index); // Update index of last element
list.remove(list.size() - 1); // Remove last element
map.remove(val); // Remove from map
return true;
}
public int getRandom() {
return list.get(random.nextInt(list.size())); // Get random element
}
}Line-By-Line Explanation
Step 1: Create Properties
class RandomizedSet {
private Map<Integer, Integer> map; // Maps value -> index in ArrayList
private List<Integer> list; // Stores the actual values
private Random random;1. A HashMap (map) to map values to their indices in the list.
2. An ArrayList (list) to store the values for easy access and random retrieval.
3. A Random object (random) to generate random indices.
Step 2: Initialize Data Sructures
public RandomizedSet() {
map = new HashMap<>();
list = new ArrayList<>();
random = new Random();
}- Sets up the data structures required for the operations (insert, remove, and getRandom).
Step 3: Insert Method
public boolean insert(int val) {
if (map.containsKey(val)) return false; // Value already exists
map.put(val, list.size()); // Add value and its index
list.add(val); // Add value to ArrayList
return true;
}- Uses map.containsKey(val) to check if the value is already in the set.
- Adds the value to the list and updates the map with its index.
Step 4: Remove Method
public boolean remove(int val) {
if (!map.containsKey(val)) return false; // Value not present
int index = map.get(val); // Get index of value
int lastVal = list.get(list.size() - 1); // Get last element in list
list.set(index, lastVal); // Swap with last element
map.put(lastVal, index); // Update index of last element
list.remove(list.size() - 1); // Remove last element
map.remove(val); // Remove from map
return true;
}- Verify the value is in the map using contains key
- Gets the index of the value and the last value in the list. Value must be swapped with the last element to enable O(1) removal.
- Overwrites the value at index with lastVal in the list and updates its index in the map.
- Removes the last element from the list and deletes the mapping from the map.
- Maintains a compact list without shifting element, ensuring O(1) deletion.
Step 5: getRandom Method
public int getRandom() {
return list.get(random.nextInt(list.size())); // Get random element
}- Uses random.nextInt(list.size()) to generate a random integer between 0 and list.size() – 1.
- Ensures a uniform random selection of elements.
Why This Code Works
Using a HashMap and ArrayList together is a powerful pattern in competitive programming and practical coding. While an ArrayList alone is sufficient for simple storage and access, the addition of a HashMap transforms it into a versatile data structure capable of supporting complex operations with ease. By leveraging the strengths of both, we achieve an elegant solution to problems that demand efficiency and flexibility.
