LeetCode 380: Insert Delete GetRandom O(1) — Python Solution

Solve LeetCode 380: Insert Delete GetRandom O(1) in Python with a array plus index map approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

What the problem is testing

Store values densely in an array and map each value to its index. Removal swaps the target with the last value before popping.

Algorithm

1. Store values densely in an array and map each value to its index. Removal swaps the target with the last value before popping.
2. Maintain this invariant: The map always records the current array index of every stored value.
3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

Python solution

from collections import Counter, defaultdict, deque, OrderedDict
import random

class RandomizedSet:
    def __init__(self):
        self.values = []
        self.index = {}

    def insert(self, val):
        if val in self.index:
            return False
        self.index[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val):
        if val not in self.index:
            return False
        i = self.index.pop(val)
        last = self.values.pop()
        if i < len(self.values):
            self.values[i] = last
            self.index[last] = i
        return True

    def getRandom(self):
        return random.choice(self.values)

Why this is correct

The proof follows the maintained state: The map always records the current array index of every stored value. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

Complexity

O(1) average time per operation and O(n) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

Edge cases

Removing the final element and reinserting a deleted value must update both structures.

Tested reference code

This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 274. H-Index · Next: 238. Product of Array Except Self