Solution: Insert Delete GetRandom O(1)

Let's solve the Insert Delete GetRandom O(1) problem using the Custom Data Structures pattern.

We'll cover the following

Statement

Implement a Random Set data structure that can perform the following operations:

  • Constructor(): This initializes the Random Set object.
  • Insert(): This function takes an integer, data, as its parameter and, if it does not already exist in the set, add it to the set, returning TRUE. If the integer already exists in the set, the function returns FALSE.
  • Delete(): This function takes an integer, data, as its parameter and, if it exists in the set, removes it, returning TRUE. If the integer does not exist in the set, the function returns FALSE.
  • GetRandom(): This function takes no parameters. It returns an integer chosen at random from the set.

Note: Your implementation should aim to have a running time of O(1)O(1) (on average) for each operation.

Constraints:

  • −231≤-2^{31} \leq data ≤231\leq 2^{31}
  • No more than 2×1052 \times 10^5 calls will be made to the Insert(), Delete() and GetRandom() functions.
  • There will be at least one element in the data structure when the GetRandom() function is called.

Solution

So far, you’ve probably brainstormed some approaches on how to solve this problem. Let’s explore some of these approaches and figure out which one to follow while considering time complexity and any implementation constraints.

Naive approach

The naive approach to solve this problem is by using an array. Elements can be inserted and deleted from an array. Random values from an array can also be fetched by getting a random index first and then retrieving the array element.

The time complexity for this approach will be O(n)O(n), but our approach should have a running time of O(1)O(1) (on average) for each operation. Although the array supports constant time lookups, the deletion takes O(n)O(n) time. Clearly, we need to look for a better approach.

Optimized approach using an array and a hash map

This problem can’t be solved using a standard data structure, so we’ll need to design a custom data structure that meets these requirements. Arrays support constant time lookups, but deletion takes O(n)O(n). A data structure that supports constant time deletion is the hash map. So, we’ll use arrays and hash maps to design our custom data structure.

Let’s consider the data structures with constant-time lookups, such as arrays and hash maps. Both of these data structures have their own advantages. To benefit from both, we’ll create a hybrid data structure to store the elements.

  • Insert(): When inserting data, we will store the new element in our array. And then, insert a key-value pair in our hash map, where the key will be the new element and the value will be its index in the array. Both of these operations have a time complexity of O(1)O(1).

  • Delete(): Using the hash map, we find the index in the array at which the element is located. Swap the last element in the array with the one to be removed. Then, in the hash map, update the location of the element we just swapped with the target element, and remove the entry for the target element from the hash map. Lastly, pop out the target element from the array. Each of these five operations has a time complexity of O(1)O(1).

  • GetRandom(): For this operation, we can choose a number at random between 00 and n−1n-1, where nn is the size of the array. We return the integer located at this random index.

The slides below illustrate how our custom data structure will work:

Let’s take a look at the code for this solution below:

import java.util.*;
class RandomSet{
    Map<Integer, Integer> dict;
    List<Integer> list;
    Random rand = new Random();
    /** Initialize your data structure here. */
    public RandomSet() {
        dict = new HashMap<>(); 
        list = new ArrayList<>(); 
    }
    /** Inserts a value to the dataset. Returns true if the dataset 
    did not already contain the specified value. */
    public boolean insert(int val) {
        if (dict.containsKey(val)) 
            return false;
        dict.put(val, list.size());
        list.add(list.size(), val);
        return true;
    }
    /** Deletes a value from the dataset. Returns true if the dataset 
    contained the specified value. */
    public boolean delete(int val) {
        if (! dict.containsKey(val)) 
            return false;
        int last = list.get(list.size() - 1);
        int index = dict.get(val);
        list.set(index, last);
        dict.put(last, index);
        list.remove(list.size() - 1);
        dict.remove(val);
        return true;
    }
    /** Get a random value from the dataset. */
    public int getRandomData() {
        return list.get(rand.nextInt(list.size()));
    }
    public static void main (String args[]){
        char[][] commands = {{'I', 'G', 'I', 'I', 'R', 'G'},
                {'I', 'I', 'R', 'G', 'R', 'I'}};
        int[][] values = {{10, -1, 100, 1000, 200, -1}, {30, 60, 10, -1, 30, 90}};
        for(int i=0;i<commands.length;i++)
        {
            RandomSet dataset = new RandomSet();
            System.out.println((i+1)+ ". Starting operations:");
            for(int j=0;j<commands[i].length;j++){
                if (commands[i][j] == 'I'){
                    System.out.println("\tInsert ("+ values[i][j]+ ") returns "+ dataset.insert(values[i][j]));
                }
                else if (commands[i][j] == 'R'){
                    System.out.println("\tDelete ("+ values[i][j]+ ") returns "+ dataset.delete(values[i][j]));
                }
                else if (commands[i][j] == 'G'){
                    System.out.println("\tGenerate Random() returns "+ dataset.getRandomData());
                }
                else {
                    
                }
            }
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Insert Delete GetRandom O(1)

Solution summary

To recap, the solution to this problem is:

For our setup, we store our data in an array and the location of each data element in a hash map.

  • For insertion:
    • We append an element to the array.
    • Now we insert the key-value pair in the hash map where the key is the element and its value is the element’s index in the array.
  • For deletion:

    • We use a hash map to find the index at which the element is located in our array.

    • After finding the position of the element in an array, swap the last element in the array with the one to be deleted.

    • Update the relevant key-value pair in the hash map so that its value is the new index of the element we just swapped with the target element.

    • Delete the key-value pair of the target element from the hash map and then delete the target element from our array.

  • To get a random element, generate a random number in the range up to the amount of elements stored, and return the element in the array at this random index.

Time complexity

  • Constructor: The time complexity of the constructor is O(1)O(1).
  • Insert() has an average time complexity of O(1)O(1). We append the element to the end of the array and insert a key-value pair in a hash map, both of which are, on average, O(1)O(1) operations.
  • Delete() has an average time complexity of O(1)O(1). We swap the value to delete with the value at the last index of the array. We update the index of the moved element in the hash map, and then pop out the value to remove from the end of the array. Each of these three operations has an average time complexity of O(1)O(1).
  • GetRandom() has an average time complexity of O(1)O(1). We pick a number at random in the range between the lowest and highest indices of the array and use it as an index in the array. Both of these are O(1)O(1) operations.

Please note that the worst-case scenario for Insert() is O(n)O(n), which occurs when space needs to be reallocated. This solution fulfills the stated requirements because the average time complexity remains O(1)O(1).

Space complexity

The data structure uses O(n)O(n) additional space to enable an average time complexity of O(1)O(1) for all of its supported operations.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.