380. Insert Delete GetRandom O(1)

MediumDesignArrayHash TableMathRandomized
Leetcode Link

Problem Description

The RandomizedSet class is designed to perform operations on a collection of unique elements. It allows for the insertion and removal of elements and getting a random element from the set. The class methods which are required to be implemented are as follows:

  • insert(val): Adds the val to the set if it's not already present, and returns true; if val is already in the set, it returns false.
  • remove(val): Removes the val from the set if it's present and returns true; if val is not present in the set, it returns false.
  • getRandom(): Returns a random element from the set, ensuring each element has an equal probability of being selected.

The constraint given is that each function should operate in average constant time, i.e., O(1) time complexity.

Intuition

The challenge lies in achieving O(1) time complexity for each operation - insert, remove, and getRandom. A standard set data structure wouldn’t suffice for getRandom() to be O(1). For efficient random access, we need to use a list structure where random access is O(1). However, a list alone does not provide O(1) time complexity for insert and remove operations due to potential shifting of elements. To navigate this, we use a combination of a hash table (dictionary in Python) and a dynamic array (list in Python).

For insertion, a dynamic array (list) supports adding an element in O(1) time. To handle duplicates, we accompany the list with a hash table that stores elements as keys and their respective indices in the list as values. This simultaneously checks for duplicates and maintains the list of elements.

For removals, a list doesn't remove an element in O(1) time because it might have to shift elements. To circumvent this, we swap the element to be removed with the last element and then pop the last element from the list. This way, the removal doesn't require shifting all subsequent elements. After swapping and before popping, we must update the hash table accordingly to reflect the new index of the element that was swapped.

Getting a random element efficiently is accomplished with a list since we can access elements by an index in O(1) time. Since all elements in the set have an equal probability of being picked, we can select a random index and return the element at that index from the list.

Overall, the use of both data structures allows us to maintain the average constant time complexity constraint required by the problem for all operations, giving us an efficient solution that meets the problem requirements.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The solution approach utilizes a blend of data structures and careful bookkeeping to ensure that each operation—insert, remove, and getRandom—executes in average constant O(1) time complexity.

Algorithms and Data Structures:

  • Hash Table/Dictionary (self.d): This hash table keeps track of the values as keys and their corresponding indices in the dynamic array as values. The hash table enables O(1) access time for checking if a value is already in the set and for removing values by looking up their index.
  • Dynamic Array/List (self.q): The dynamic array stores the elements of the set and allows us to utilize the O(1) access time to get a random element.

insert Implementation:

  • Check if val is already in the self.d hash table. If it is, return false because no duplicate values are allowed in the set.
  • If val is not present, add val as a key to self.d with the value being the current size of the list self.q (which will be the index of the inserted value).
  • Then, append val to the list self.q.
  • Return true because a new value has been successfully inserted into the set.

remove Implementation:

  • Check if val is present in the self.d hash table. If not, return false because there's nothing to remove.
  • If val is present, locate its index i in self.q using self.d[val].
  • Swap the value val in self.q with the last element in self.q to move val to the end of the list for O(1) removal.
  • The hash table self.d needs to be updated to reflect the new index for the value that was swapped to the position previously held by val.
  • Pop the last element from self.q, which is now val.
  • Remove val from the hash table self.d.
  • Return true because the value has been successfully removed from the set.

getRandom Implementation:

  • Use Python's choice function from the random module to select a random element from the list self.q. The choice function inherently operates in O(1) time complexity because it selects an index randomly and returns the element at that index from the list.

This approach essentially provides an efficient and elegant solution to conduct insert, remove, and getRandom operations on a set with constant average time complexity, fulfilling the problem's constraints using the combination of a hash table with a dynamic array.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

  1. Initialize:

    • We start by initializing our RandomizedSet. Both the dynamic array self.q and the hash table self.d are empty.

  2. Insert 5:

    • Call insert(5). Since 5 is not in self.d, we add it with its index to self.d (i.e., self.d[5] = 0) and append it to self.q (i.e., self.q = [5]).
    • The operation returns true.

  3. Insert 10:

    • Call insert(10). Similarly, since 10 is not in self.d, we add it with the next index to self.d (i.e., self.d[10] = 1) and append it to self.q (i.e., self.q = [5, 10]).
    • The operation returns true.

  4. Insert 5 again:

    • Call insert(5). Since 5 is already in self.d, we do not add it to self.q and return false.

  5. Get a random element:

    • Call getRandom(). The function could return either 5 or 10, each with a 50% probability.

  6. Remove 5:

    • Call remove(5). We find the index of 5 from self.d, which is 0. We then swap self.q[0] (5) with the last element in self.q (which is 10), resulting in self.q = [10, 5].
    • We update self.d to reflect the swap (now self.d[10] = 0), pop the last element in self.q (removing 5), and delete self.d[5].
    • The operation returns true.

  7. Current state:

    • The dynamic array self.q now holds [10], and self.d holds {10: 0}.

This simple example demonstrates the processes of each operation and how the combination of a hash table and a dynamic array can achieve O(1) average time complexity for insertions, removals, and accessing a random element.

Solution Implementation

1from random import choice
2
3class RandomizedSet:
4    def __init__(self):
5        self.index_dict = {}  # Mapping of values to their indices in the array
6        self.values_list = []  # Dynamic array to hold the values
7
8    def insert(self, val: int) -> bool:
9        # Insert the value into the set if it's not already present, returning True if successful
10        if val in self.index_dict:
11            return False  # Value already exists
12        self.index_dict[val] = len(self.values_list)  # Map value to its index in the array
13        self.values_list.append(val)  # Add value to the array
14        return True  # Insertion successful
15
16    def remove(self, val: int) -> bool:
17        # Remove the value from the set if present, returning True if successful
18        if val not in self.index_dict:
19            return False  # Value does not exist
20        index_to_remove = self.index_dict[val]  # Get the index of the value to remove
21        last_element = self.values_list[-1]  # Get the last element in the array
22        self.values_list[index_to_remove] = last_element  # Move the last element to the 'removed' position
23        self.index_dict[last_element] = index_to_remove  # Update the last element's index
24        self.values_list.pop()  # Remove the last element
25        del self.index_dict[val]  # Remove the value from the dictionary
26        return True  # Removal successful
27
28    def getRandom(self) -> int:
29        # Return a random value from the set
30        return choice(self.values_list)  # Randomly select and return a value from the array
31
32# Example usage:
33# randomized_set = RandomizedSet()
34# param_1 = randomized_set.insert(val)
35# param_2 = randomized_set.remove(val)
36# param_3 = randomized_set.getRandom()
37
1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5import java.util.Random;
6
7// RandomizedSet design allows for O(1) time complexity for insertion, deletion and getting a random element.
8class RandomizedSet {
9    private Map<Integer, Integer> valueToIndexMap = new HashMap<>(); // Maps value to its index in 'valuesList'.
10    private List<Integer> valuesList = new ArrayList<>(); // Stores the values.
11    private Random randomGenerator = new Random(); // Random generator for getRandom() method.
12
13    // Constructor of the RandomizedSet.
14    public RandomizedSet() {
15    }
16
17    // Inserts a value to the set. Returns true if the set did not already contain the specified element.
18    public boolean insert(int val) {
19        if (valueToIndexMap.containsKey(val)) {
20            // If the value is already present, return false.
21            return false;
22        }
23        // Map the value to the size of the list which is the future index of this value.
24        valueToIndexMap.put(val, valuesList.size()); 
25        // Add the value to the end of the values list.
26        valuesList.add(val); 
27        return true;
28    }
29
30    // Removes a value from the set. Returns true if the set contained the specified element.
31    public boolean remove(int val) {
32        if (!valueToIndexMap.containsKey(val)) {
33            // If the value is not present, return false.
34            return false;
35        }
36        // Get index of the element to remove.
37        int indexToRemove = valueToIndexMap.get(val); 
38        // Get last element in the list.
39        int lastElement = valuesList.get(valuesList.size() - 1); 
40        // Move the last element to the place of the element to remove.
41        valuesList.set(indexToRemove, lastElement);
42        // Update the map with the new index of lastElement.
43        valueToIndexMap.put(lastElement, indexToRemove); 
44        // Remove the last element from the list.
45        valuesList.remove(valuesList.size() - 1); 
46        // Remove the entry for the removed element from the map.
47        valueToIndexMap.remove(val);
48        return true;
49    }
50
51    // Get a random element from the set.
52    public int getRandom() {
53        // Returns a random element using the random generator.
54        return valuesList.get(randomGenerator.nextInt(valuesList.size())); 
55    }
56
57    // The below comments describe how your RandomizedSet class could be used:
58    // RandomizedSet obj = new RandomizedSet();
59    // boolean param_1 = obj.insert(val);
60    // boolean param_2 = obj.remove(val);
61    // int param_3 = obj.getRandom();
62}
63
1#include <vector>
2#include <unordered_map>
3#include <cstdlib>
4
5class RandomizedSet {
6public:
7    RandomizedSet() {
8        // Constructor doesn't need to do anything since the vector and 
9        // unordered_map are initialized by default
10    }
11
12    // Inserts a value to the set. Returns true if the set did not already contain the specified element
13    bool insert(int val) {
14        if (indexMap.count(val)) {
15            // Value is already in the set, so insertion is not possible
16            return false;
17        }
18        indexMap[val] = values.size(); // Map value to its index in 'values'
19        values.push_back(val);         // Add value to the end of 'values'
20        return true;
21    }
22
23    // Removes a value from the set. Returns true if the set contained the specified element
24    bool remove(int val) {
25        if (!indexMap.count(val)) {
26            // Value is not in the set, so removal is not possible
27            return false;
28        }
29      
30        int index = indexMap[val];               // Get index of the element to remove
31        indexMap[values.back()] = index;         // Map last element's index to the index of the one to be removed
32        values[index] = values.back();           // Replace the element to remove with the last element
33        values.pop_back();                       // Remove last element
34        indexMap.erase(val);                      // Remove element from map
35      
36        return true;
37    }
38
39    // Gets a random element from the set
40    int getRandom() {
41        return values[rand() % values.size()]; // Return a random element by index
42    }
43
44private:
45    std::unordered_map<int, int> indexMap; // Maps value to its index in 'values'
46    std::vector<int> values;               // Stores the actual values
47};
48
49/**
50 * Your RandomizedSet object will be instantiated and called as such:
51 * RandomizedSet* obj = new RandomizedSet();
52 * bool param_1 = obj->insert(val);
53 * bool param_2 = obj->remove(val);
54 * int param_3 = obj->getRandom();
55 */
56
1// Store the number and its corresponding index in the array
2let valueToIndexMap: Map<number, number> = new Map();
3// Store the numbers for random access
4let valuesArray: number[] = [];
5
6// Inserts a value to the set. Returns true if the set did not already contain the specified element.
7function insert(value: number): boolean {
8    if (valueToIndexMap.has(value)) {
9        // Value already exists, so insertion is not done
10        return false;
11    }
12    // Add value to the map and array
13    valueToIndexMap.set(value, valuesArray.length);
14    valuesArray.push(value);
15    return true;
16}
17
18// Removes a value from the set. Returns true if the set contained the specified element.
19function remove(value: number): boolean {
20    if (!valueToIndexMap.has(value)) {
21        // Value does not exist; hence, nothing to remove
22        return false;
23    }
24    // Get index of the value to be removed
25    const index = valueToIndexMap.get(value)!;
26    // Move the last element to fill the gap of the removed element
27    // Update the index of the last element in the map
28    valueToIndexMap.set(valuesArray[valuesArray.length - 1], index);
29    // Swap the last element with the one at the index
30    valuesArray[index] = valuesArray[valuesArray.length - 1];
31    // Remove the last element
32    valuesArray.pop();
33    // Remove the entry for the removed value from the map
34    valueToIndexMap.delete(value);
35    return true;
36}
37
38// Get a random element from the set.
39function getRandom(): number {
40    // Choose a random index and return the element at that index
41    return valuesArray[Math.floor(Math.random() * valuesArray.length)];
42}
43
44// Usage example:
45// var successInsert = insert(3); // returns true
46// var successRemove = remove(3); // returns true
47// var randomValue = getRandom(); // returns a random value from the set
48
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Time and Space Complexity

Time Complexity:

  • insert(val: int) -> bool: The insertion function consists of a dictionary check and insertion into a dictionary and a list, which are typically O(1) operations. Thus, the time complexity is O(1).
  • remove(val: int) -> bool: The remove function performs a dictionary check, index retrieval, and element swap in the list, as well as removal from both the dictionary and list. Dictionary and list operations involved here are usually O(1). Therefore, the time complexity is O(1).
  • getRandom() -> int: The getRandom function makes a single call to the choice() function from the Python random module, which selects a random element from the list in O(1) time. Hence, the time complexity is O(1).

Overall, each of the operations provided by the RandomizedSet class have O(1) time complexity.

Space Complexity:

  • The RandomizedSet class maintains a dictionary (self.d) and a list (self.q). The dictionary maps element values to their indices in the list, and both data structures store up to n elements, where n is the total number of unique elements inserted into the set. Hence, the space complexity is O(n), accounting for the storage of n elements in both the dictionary and the list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How many ways can you arrange the three letters A, B and C?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫