⚡Flashcard Drill➔
NeetCode #127LC-380MediumArrays & Hashing
← Back to All Problems

#127 · #380 · Insert Delete GetRandom O(1)(O(1) 时间插入、删除和获取随机元素)

📌 Problem Statement & Constraints

Design a data structure that supports insert(val), remove(val) and getRandom() in average O(1) time. insert returns whether the value was newly added, remove returns whether the value existed, and getRandom returns a uniformly random existing element. Constraints: -2^31 <= val <= 2^31 - 1; at most 2 * 10^5 calls.

💡 Core Algorithmic Approaches

  1. An array alone gives O(1) random access but O(n) removal; a hash map alone gives O(1) insert/remove but cannot sample uniformly without materialising the keys.
  2. Combine them: the array stores the values, and the map stores each value's index in the array.
  3. remove(val) swaps the target with the last element, updates the moved element's index, then pops the array -- O(1) overall.
  4. getRandom picks a uniform index with random.choice, which is O(1).

💻 Benchmark Python3 Implementation

import random

class RandomizedSet:
    def __init__(self):
        self.arr = []                      # the values
        self.pos = {}                      # value -> index in arr

    def insert(self, val: int) -> bool:
        if val in self.pos:
            return False
        self.pos[val] = len(self.arr)
        self.arr.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.pos:
            return False
        i = self.pos[val]
        last = self.arr[-1]
        self.arr[i] = last                 # move the last element into the hole
        self.pos[last] = i
        self.arr.pop()
        del self.pos[val]                  # must come after the reassignment
        return True

    def getRandom(self) -> int:
        return random.choice(self.arr)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) average per operation: array append/pop are amortised O(1) and hash operations are O(1) on average.
💾 Space Complexity
O(n) for the array and the index map.

⚠️ Interview Pitfalls & Follow-ups

  • Deleting from the map before moving the last element: when the removed value is the last element, self.pos[last] = i would recreate the entry you just deleted. Order matters.
  • Removing from the array with arr.remove(val): O(n) because of the shift.
  • Using set and converting to a list in getRandom: O(n) per call.
  • Forgetting to update the moved element's index: the map would point at a stale position, breaking later removals.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems