Insert Delete GetRandom O(1)

You can implement the RandomizedSet class by maintaining a dictionary that maps the values to their indexes in a list and a list containing the values. This structure allows for constant-time access, insertion, and removal. The random module can be used to select a random element from the list.

Here’s the implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import random

class RandomizedSet:

    def __init__(self):
        self.val_to_index = {}  # Dictionary to store the indexes of the values
        self.values = []        # List to store the values

    def insert(self, val: int) -> bool:
        if val in self.val_to_index: # Check if the value is already present
            return False
        self.values.append(val) # Append value to the list
        self.val_to_index[val] = len(self.values) - 1 # Update the dictionary with the index
        return True

    def remove(self, val: int) -> bool:
        if val not in self.val_to_index: # Check if the value is not present
            return False
        index = self.val_to_index[val] # Get the index of the value to be removed
        last_val = self.values[-1] # Get the last value in the list

        # Swap the value to be removed with the last value
        self.values[index] = last_val
        self.val_to_index[last_val] = index

        # Remove the last value from the list and dictionary
        self.values.pop()
        del self.val_to_index[val]

        return True

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

Explanation:

  • Initialization (__init__ method): This initializes an empty dictionary and list to manage the set.

  • Inserting a Value (insert method): This method inserts a value into the set if it is not already present.

  • Removing a Value (remove method): This method removes a value from the set if it is present. The removal process involves swapping the value with the last element in the list and then removing the last element. This ensures constant-time removal.

  • Getting a Random Value (getRandom method): This method returns a random value from the set using the random.choice method.

All operations in this implementation have average O(1) time complexity, as required by the problem statement.

Problem Definition

Define the Terms

Define the Interface

  Input: 
  Output:
Identify Implicit Inputs

Define the Goal

Identify the Constraints

-2^31 <= val <= 2^31 - 1 At most 10^5 calls will be made to insert, remove, and getRandom. There will be at least one element in the data structure when getRandom is called.

Determine the Scope

  • List assumptions
  • Define boundaries of the problem

Search the Problem Space

  • Look for clues in the problem statement

Classify the Problem

  • Decontextualize the Problem

  • Can you think of this problem in a different way?

  • Can you reframe it?

Problem Representation

  • Analyze the Input and Output

  • Analyze the Examples

Solve the Problem by Hand

Recognize the Pattern

Identify the Invariants

Brainstorm Solutions

  • Brute Force Approach

  • Shortcomings

  • Evaluate and Select Approach

Analyze Time and Space Complexity

  • Time: O( )
  • Space: O( )

Outline the Solution

Key Takeaways

Reflect

  • What went right?

  • What went wrong?

  • What can we improve next time?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class RandomizedSet

=begin
    Initialize your data structure here.
=end
    def initialize()
      @set = Set.new
    end


=begin
    Inserts a value to the set. Returns true if the set did not already contain the specified element.
    :type val: Integer
    :rtype: Boolean
=end
    def insert(val)
       result = @set.include?(val)

       @set.add(val)

       return !result 
    end


=begin
    Removes a value from the set. Returns true if the set contained the specified element.
    :type val: Integer
    :rtype: Boolean
=end
    def remove(val)
       result = @set.include?(val)
       @set.delete(val)

        return result
    end


=begin
    Get a random element from the set.
    :rtype: Integer
=end
    def get_random()
       @set.to_a.sample
    end
end

# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet.new()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.get_random()