How to Achieve O(1) Insert, Delete, and GetRandom Operations in a Collection

Combine a HashMap with an ArrayList and use the swap-with-last technique to achieve O(1) average time complexity for insert, delete, and getRandom operations in a collection.

The kdn251/interviews repository demonstrates this classic algorithmic pattern in leetcode/design/InsertDeleteGetRandomO1.java. This solution addresses the common interview requirement of designing a data structure that supports insertion, deletion, and random retrieval—all in constant time.

The Data Structure Combination for O(1) Operations

Achieving O(1) for all three operations requires combining two standard data structures. Neither alone can satisfy all constraints simultaneously.

Why HashMap and ArrayList?

• HashMap<Integer, Integer>: Stores the mapping from value to its current index in the ArrayList. This provides O(1) lookups to find where an element resides.
• ArrayList: Stores the actual values in a contiguous array, enabling O(1) random access by index and O(1) amortized insertion at the end.

Using only a HashSet would provide O(1) insert and delete, but retrieving a random element would require O(n) time to convert to an array or iterate. Using only an ArrayList would make deletion O(n) due to shifting elements.

Implementing O(1) Insert, Delete, and GetRandom

O(1) Insertion

Insertion appends the value to the end of the ArrayList and records its index in the HashMap.

public boolean insert(int val) {
    if (idxMap.containsKey(val)) return false;
    idxMap.put(val, values.size());
    values.add(val);
    return true;
}

Both HashMap.put() and ArrayList.add() operate in O(1) average time.

O(1) Deletion with the Swap-With-Last Technique

Deletion is the critical operation. Instead of removing from the middle (which would shift elements and cost O(n)), the algorithm swaps the target element with the last element, updates the HashMap for the moved element, then removes the tail.

public boolean remove(int val) {
    Integer idx = idxMap.get(val);
    if (idx == null) return false;

    int lastVal = values.get(values.size() - 1);
    values.set(idx, lastVal);          // Move last element to deleted position
    idxMap.put(lastVal, idx);            // Update index of moved element

    values.remove(values.size() - 1);     // Remove last element (now duplicate)
    idxMap.remove(val);
    return true;
}

This ensures no shifting occurs, maintaining O(1) time complexity.

O(1) GetRandom Access

Random retrieval leverages the ArrayList's direct indexing capability.

public int getRandom() {
    int randomIdx = (int) (Math.random() * values.size());
    return values.get(randomIdx);
}

Generating a random index and accessing by that index are both O(1) operations.

Complete Java Implementation from kdn251/interviews

The kdn251/interviews repository provides the full implementation in leetcode/design/InsertDeleteGetRandomO1.java. This file demonstrates the production-ready version of the pattern described above.

// File: leetcode/design/InsertDeleteGetRandomO1.java
// https://github.com/kdn251/interviews/blob/master/leetcode/design/InsertDeleteGetRandomO1.java

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

class RandomizedSet {
    private final HashMap<Integer, Integer> idxMap;
    private final ArrayList<Integer> values;
    private final Random rand;

    public RandomizedSet() {
        idxMap = new HashMap<>();
        values = new ArrayList<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        if (idxMap.containsKey(val)) {
            return false;
        }
        idxMap.put(val, values.size());
        values.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!idxMap.containsKey(val)) {
            return false;
        }
        int idx = idxMap.get(val);
        int lastVal = values.get(values.size() - 1);
        
        values.set(idx, lastVal);
        idxMap.put(lastVal, idx);
        
        values.remove(values.size() - 1);
        idxMap.remove(val);
        return true;
    }

    public int getRandom() {
        return values.get(rand.nextInt(values.size()));
    }
}

The repository also contains variations of this implementation in leetcode/hash-table/ and leetcode/array/ directories, demonstrating how the same pattern applies across different categorizations.

Usage Example

Here is how to use the RandomizedSet class to perform O(1) operations:

public class Demo {
    public static void main(String[] args) {
        RandomizedSet set = new RandomizedSet();
        
        // Insert operations
        System.out.println(set.insert(10)); // true (element added)
        System.out.println(set.insert(20)); // true (element added)
        System.out.println(set.insert(10)); // false (duplicate)
        
        // Random access
        System.out.println("Random: " + set.getRandom()); // Returns 10 or 20
        
        // Delete operations
        System.out.println(set.remove(10)); // true (element removed)
        System.out.println(set.remove(30)); // false (not found)
        
        // Random still O(1) after deletion
        System.out.println("Random after removal: " + set.getRandom()); // Returns 20
    }
}

Summary

• Combine HashMap and ArrayList to achieve O(1) insert, delete, and getRandom operations in a collection.
• HashMap stores value-to-index mappings for O(1) lookups, while ArrayList provides O(1) random access and amortized O(1) insertion at the end.
• Swap-with-last technique enables O(1) deletion by moving the last element to the deleted position, avoiding the O(n) cost of shifting elements.
• The kdn251/interviews repository implements this pattern in leetcode/design/InsertDeleteGetRandomO1.java, providing a production-ready reference for interview preparation.

Frequently Asked Questions

Why can't I use a HashSet alone for O(1) insert, delete, and getRandom?

A HashSet provides O(1) insertion and deletion, but retrieving a random element requires O(n) time because hash tables do not support index-based access. You would need to iterate through the set or convert it to an array, both of which violate the O(1) requirement for getRandom.

Does the swap-with-last technique affect the randomness of getRandom?

No, the swap-with-last technique does not compromise randomness. The ArrayList maintains a dense packing of elements with no gaps, ensuring that every valid index from 0 to size-1 contains an active element. When getRandom generates a uniform random index across this range, each remaining element has an equal probability of selection regardless of how the internal ordering changed during previous deletions.

What is the space complexity of this O(1) data structure?

The space complexity is O(n), where n is the number of elements stored. The HashMap stores one entry per element (value to index), and the ArrayList stores one Integer object per element. Both structures maintain parallel data for every inserted item, resulting in linear space overhead relative to the collection size.

Can this pattern be extended to support duplicate values?

Yes, but it requires modifying the data structure to track multiple indices per value. Instead of mapping Integer -> Integer, the HashMap would map Integer -> Set<Integer> or Integer -> List<Integer> to store all indices where a value appears. During deletion, you would remove one arbitrary index from the set and apply the swap-with-last logic, updating the moved element's index collection accordingly. This maintains O(1) amortized complexity while allowing duplicates.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}