algoadvance

Leetcode 380. Insert Delete GetRandom O(1)

Problem Statement

Design a data structure that supports all following operations in average O(1) time.

1. insert(val): Inserts an item val into the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. getRandom(): Returns a random element from the current set of elements. Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always returns 2.
randomSet.getRandom();

Clarifying Questions

1. Can the same value be inserted multiple times?
   • No, each value should be unique within the set.
2. What should be returned if we try to remove a value that does not exist?
   • Return false.
3. What if the set is empty when calling getRandom()?
   • It is guaranteed that getRandom() will only be called if there is at least one item in the set.
4. Should the getRandom() method have any specific random criteria?
   • Each element must have the same probability of being returned.

Strategy

To achieve average O(1) time complexity for insert, remove, and getRandom operations, we can use a combination of a list and a hash map:

1. List (ArrayList):
   • Store the elements to facilitate O(1) time for getRandom() by using the size of the list to generate a random index.
2. HashMap:
   • The key will be the element value, and the value will be the index of the element in the list.
   • This allows for O(1) access and deletion operations.

Detailed Steps:

• Insert:
  • If the element exists in the hash map, return false.
  • Otherwise, add the element to the end of the list and update the hash map.
• Remove:
  • If the element does not exist in the hash map, return false.
  • Swap the element with the last element of the list to facilitate O(1) removal.
  • Update the list and hash map accordingly, then remove the last element of the list.
• GetRandom:
  • Use Java’s Random class to select a random index from the list.

Code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

public class RandomizedSet {
    private ArrayList<Integer> nums;
    private HashMap<Integer, Integer> numToIndex;
    private Random random;
    
    /** Initialize your data structure here. */
    public RandomizedSet() {
        nums = new ArrayList<>();
        numToIndex = new HashMap<>();
        random = new Random();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (numToIndex.containsKey(val)) {
            return false;
        }
        nums.add(val);
        numToIndex.put(val, nums.size() - 1);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!numToIndex.containsKey(val)) {
            return false;
        }
        int index = numToIndex.get(val);
        int lastElement = nums.get(nums.size() - 1);
        
        // Swap the last element with the element to remove
        nums.set(index, lastElement);
        numToIndex.put(lastElement, index);
        
        // Remove the last element
        nums.remove(nums.size() - 1);
        numToIndex.remove(val);
        
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        int randomIndex = random.nextInt(nums.size());
        return nums.get(randomIndex);
    }
}

Time Complexity

• Insert: Average O(1) - Access and update both the list and the hash map.
• Remove: Average O(1) - Access, update, and remove operations on both list and hash map are done in constant time.
• GetRandom: O(1) - Accessing an element at a random index in the list is O(1).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?