Press enter to see results or esc to cancel.

Insert Delete Get Random O(1) Leetcode Problem 380 [Python Solution]
CID in SOFTWARE DEVELOPMENT
  0 Comments

Insert Delete Get Random O(1) Leetcode Problem 380 [Python Solution]

In this blog post, we’re going all in to the LeetCode problem known as Insert Delete Get Random O(1) (Problem 380).

This problem falls under the category of Arrays and Hashing and is considered to be of medium difficulty.

The challenge revolves around designing a data structure that allows us to perform various operations efficiently: insert, remove, and get a random element.

We’ll walk you through a step-by-step solution, optimized for beginners, and provide a Python implementation.

By the end of this blog post, you’ll have a clear understanding of how to implement this data structure and perform these operations in constant time, on average.

Problem Overview

Let’s start by understanding the problem statement.

We are required to implement the RandomizedSet class, which supports three operations:

  1. RandomizedSet(): Initializes the RandomizedSet object.
  2. insert(val): Inserts an item val into the set if it’s not already present.

It returns true if the item was successfully inserted (i.e., it wasn’t already in the set), and false otherwise.

  1. remove(val): Removes an item val from the set if it’s present.

It returns true if the item was successfully removed, and false otherwise.

  1. getRandom(): Returns a random element from the current set of elements.

It’s guaranteed that at least one element exists when this method is called, and each element must have an equal probability of being returned.

The key requirement is that each of these operations should work in average O(1) time complexity.

Problem Overview

To tackle this problem effectively, we need to implement a data structure that can handle insertions, removals, and random element retrieval efficiently.

Let’s break down the problem step by step.

Example 1:

Before we dive into the solution, let’s explore the problem using an example.

This will help us understand the intricacies of the operations.

Suppose we have the following sequence of operations:

randomizedSet = RandomizedSet()
randomizedSet.insert(1)  # Inserts 1 to the set.

Returns true.

randomizedSet.remove(2)  # Returns false as 2 doesn't exist in the set.

randomizedSet.insert(2)  # Inserts 2 to the set, returns true.

Set now contains [1, 2].

randomizedSet.getRandom()  # Should return either 1 or 2 randomly.

randomizedSet.remove(1)  # Removes 1 from the set, returns true.

Set now contains [2].

randomizedSet.insert(2)  # 2 was already in the set, so returns false.

randomizedSet.getRandom()  # Since 2 is the only number in the set, getRandom() will always return 2.

The key takeaway from this example is that we must handle insertions, removals, and random retrievals efficiently.

Understanding the Constraints

Before we delve into the implementation, let’s understand the constraints imposed by the problem:

  • The values (val) to be inserted or removed are integers within the range of -231 to 231 – 1.
  • The maximum number of calls for insert, remove, and getRandom is 2 * 105.
  • There will always be at least one element in the data structure when getRandom is called.

Now that we have a clear understanding of the problem and its constraints, let’s proceed to implement our solution.

Insert Delete Get Random O(1) LeetCode Problem Solution

We’ll implement a Python solution for this problem, step by step.

Our solution will use a combination of a dictionary (hash map) and a list to achieve the desired O(1) time complexity for insertions, removals, and random retrievals.

1. Bruteforce Approach

Let’s start with a basic implementation of the RandomizedSet class using a brute force approach.

This approach will help us understand the core data structures and methods required for the problem.

class RandomizedSet:

    def __init__(self):

        # Initialize an empty dictionary to store values and their indexes.
        self.num_map = {}

        # Initialize an empty list to store values.
        self.num_list = []

    def insert(self, val: int) -> bool:
        # Check if the value is already in the dictionary.
        if val in self.num_map:
                return False

        # If the value is not present, add it to the dictionary and list.
        self.num_map[val] = len(self.num_list)
                self.num_list.append(val)

        return True

In the brute force approach, we use a dictionary (num_map) to keep track of values and their corresponding indexes in a list (num_list).

The insert method first checks if the value already exists in the dictionary.

If it does, the function returns False since we don’t want to add duplicate values.

If the value is not present, we add it to the dictionary and append it to the end of the list, updating the index in the dictionary as well.

2. Efficient Approach with Deletion

The brute force approach we discussed above covers insertions efficiently.

However, the remove operation presents a challenge when we need to remove a value from the middle of the list.

This would require shifting all the elements after it, which takes O(n) time.

To overcome this, we’ll use a more efficient approach with deletion.

def remove(self, val: int) -> bool:
    # Check if the value exists in the dictionary.
    if val not in self.num_map:
        return False

    # Get the index of the value in the list.
    idx, last_element = self.num_map[val], self.num_list[-1]

    # Move the last element to the index of the element we want to remove.
    self.num_list[idx], self.num_map[last_element] = last_element, idx

    # Remove the value from the list and dictionary.
    self.num_list.pop()
    del self.num_map[val]

    return True

In this more efficient approach, we first check if the value exists in the dictionary (num_map).

If it does, we proceed to remove it.

To remove a value efficiently, we get its index in the list (num_list).

Then, we obtain the last element of the list, as we’ll use it to replace the element we want to remove.

By moving the last element to the index of the element we want to remove, we effectively remove the desired element without shifting all the elements in the list.

Finally, we pop the last element from the list and delete the value from the dictionary.

With these two methods, we’ve covered efficient insertions and deletions.

Now, let’s implement the getRandom method.

3. Random Retrieval

The getRandom method is relatively straightforward.

We want to return a random element from the list, ensuring that each element has an equal probability of being chosen.

We can achieve this by using Python’s random.choice function.

def getRandom(self) -> int:
        # Return a random element from the list.
        return choice(self.num_list)

The getRandom method simply uses the choice function from the random module to select a random element from the list (num_list).

Since the list is guaranteed to contain at least one element when this method is called, we’re confident that we’ll have a valid choice.

Insert Delete Get Random O(1) Solution [Python Full Code]

View on GitHub ➹
class RandomizedSet:
    def __init__(self):
        # Initialize an empty dictionary to store values and their indexes.
        self.num_map = {}

        # Initialize an empty list to store values.
        self.num_list = []

    def insert(self, val: int) -> bool:
        # Check if the value is already in the dictionary.
        if val in self.num_map:
            return False

        # If the value is not present, add it to the dictionary and list.
        self.num_map[val] = len(self.num_list)
        self.num_list.append(val)

        return True

    def remove(self, val: int) -> bool:
        # Check if the value exists in the dictionary.
        if val not in self.num_map:
            return False

        # Get the index of the value in the list.
        idx, last_element = self.num_map[val], self.num_list[-1]

        # Move the last element to the index of the element we want to remove.
        self.num_list[idx], self.num_map[last_element] = last_element, idx

        # Remove the value from the list and dictionary.
        self.num_list.pop()
        del self.num_map[val]

        return True

    def getRandom(self) -> int:
        # Return a random element from the list.
        return choice(self.num_list)

Time and Space Complexity

Now that we’ve implemented all the necessary methods for the RandomizedSet class, let’s analyze the time and space complexity of our solution.

  • Insertion (insert method): We perform insertions in O(1) time, as we only check for the presence of a value in the dictionary and append it to the list, both of which are O(1) operations.
  • Deletion (remove method): The deletion operation is also performed in O(1) time, as we efficiently replace the element to be removed with the last element and then remove the last element.

The dictionary update and deletion are also O(1) operations.

  • Random Retrieval (getRandom method): Retrieving a random element from the list is done in O(1) time using the random.choice function.
  • Space Complexity: The space complexity of our solution is O(n), where n is the number of unique elements stored in the RandomizedSet.

We use a dictionary to map elements to their indexes, which has a space complexity of O(n).

The list that stores the elements also has a space complexity of O(n).

Reasoning Behind Our Approach

Our approach efficiently addresses the key requirements of the problem, allowing us to perform insertions, removals, and random retrievals in average O(1) time complexity.

Here’s the reasoning behind our approach:

  • We use a dictionary (num_map) to store elements and their corresponding indexes in the list.

This allows us to check for the presence of a value and retrieve its index in O(1) time.

  • The list (num_list) serves as the primary data structure for storing elements.

We append new elements to the end of the list, ensuring that the most recently added element is at the end.

  • For efficient removals, we use a swap-based approach.

When we remove an element from the middle of the list, we replace it with the last element, and then we remove the last element.

This avoids shifting all elements and maintains a continuous range of indexes, crucial for O(1) time complexity.

  • Random retrievals are achieved by using Python’s random.choice function to select a random element from the list.

This provides each element with an equal probability of being chosen, meeting the problem’s requirements.

Our approach strikes a balance between efficient insertions, removals, and random retrievals, ensuring that all operations are performed in constant time, on average.

Related Interview Questions By Company:

Related Interview Questions By Difficulty:

Related Interview Questions By Category:

Conclusion

In this blog post, we tackled the LeetCode problem Insert Delete Get Random O(1) (Problem 380) with a detailed and beginner-friendly Python solution.

We implemented the RandomizedSet class, which allows us to insert, remove, and retrieve random elements efficiently.

Our approach leverages a combination of a dictionary and a list, enabling us to achieve average O(1) time complexity for all operations.

By using a swap-based deletion approach and Python’s random.choice function for random retrievals, we’ve optimized the implementation to meet the problem’s requirements.

This solution ensures that each element has an equal probability of being chosen when retrieving random elements.

We hope this blog post has provided you with a clear and insightful solution to the Insert Delete Get Random O(1) problem.

If you have any questions, comments, or suggestions, please feel free to share them.

You can also try out the code and experiment with different test cases to further solidify your understanding.

Link to the LeetCode problem

Don’t hesitate to leave comments, ask questions, make suggestions, and share this content with others who might find it helpful.

Happy coding!

Written By
CID

CID is a Software Engineer cum Digital Marketer. He launched Auditorical in 2018, a platform that empowers creators, agencies, and businesses with tools, software reviews and informational resources to create, distribute, and monetize content.

Tags
>