· By John Kavanagh

Insert, Delete, and Get a Random Value in TypeScript

Dice with red markings lie scattered on a pale tiled surface.
Image by Nika Benedictova, licensed from Unsplash.

A set makes membership convenient. An array makes choosing a random position convenient. LeetCode's Insert Delete GetRandom O(1) exercise asks for both conveniences at once, with insertion, removal, and random selection all taking average constant time.

The awkward operation is deletion. Removing an item from the middle of an ordinary array shifts later elements, and leaving a hole makes random selection unreliable. The useful freedom is that this set has no ordering promise. We can move its last element into the vacated position, then shorten the array.

I'll pair that dense array with a map from value to position. The implementation is short, but the relationship between those two structures deserves more attention than the random‑number call. A stale index can make a perfectly ordinary bookkeeping error look like a problem with the random selection.


Two Structures, One Invariant

The array contains each current value exactly once, with no gaps. The map contains exactly the same values as keys, and each mapped index points to that value in the array. If those statements remain true, all three operations have the information they need.

Insertion first asks the map whether the value already exists. If it does, return false without changing anything. Otherwise, record the array's current length as the new value's index, append the value, and return true.

Random selection chooses an index from zero through length minus one and returns the value there. Because every value occupies one position, a uniform choice of index gives every stored value the same chance. A sparse array or duplicate entry would break that correspondence, even with a perfect random generator.

Removal looks up the position directly. It replaces that position with the final array value, updates the moved value's mapped position, removes the last array slot, and deletes the removed value from the map. Those steps are the whole trick; the order matters.

class RandomizedSet {
  private readonly values: number[] = [];
  private readonly positions = new Map<number, number>();

  insert = (value: number): boolean => {
    if (this.positions.has(value)) return false;
    this.positions.set(value, this.values.length);
    this.values.push(value);
    return true;
  };

  remove = (value: number): boolean => {
    const index = this.positions.get(value);
    if (index === undefined) return false;
    const last = this.values[this.values.length - 1];
    this.values[index] = last;
    this.positions.set(last, index);
    this.values.pop();
    this.positions.delete(value);
    return true;
  };

  getRandom = (): number => {
    if (this.values.length === 0) throw new Error('The set is empty');
    return this.values[Math.floor(Math.random() * this.values.length)];
  };
}

The error on an empty set is a small defensive extension. LeetCode guarantees that getRandom is called only when an element exists. Returning undefined with a declared number type would be misleading outside that guarantee, so I prefer an explicit failure if a caller breaks it.

The method names match the exercise, including RandomizedSet with its fixed American spelling. There is no useful reason to translate an interface the judge expects. The class also accepts zero and negative numbers, because neither array positions nor map membership depend on the sign of the stored value.


The Deletion Worth Tracing

Imagine the array is [12, 40, 7], with map entries 12 to zero, 40 to one, and 7 to two. Removing 40 finds index one. The final value, 7, moves into that slot, so its map entry changes to one. Popping the array leaves [12, 7], and deleting 40 removes its map entry.

If we forget to update 7's position, the next removal of 7 reads a stale index. The previous operation may look correct when inspected only through random selection, but it has already damaged the structure. This is why a sequence of operations is more revealing than testing each method once on a fresh instance.

Now remove 7 from the two‑element array. The value being removed is already last, so the assignment writes 7 back into its own slot and the map update writes its existing position. Popping and deleting then remove it cleanly. No special final‑element branch is required.

That last case depends on deleting the removed value after updating the moved value. When they are the same value, deleting first and then updating would accidentally recreate a map entry for a value no longer in the array. The generic path is tidy because its ordering handles the overlap deliberately.


What Average Constant Time Means Here

Array indexing is constant‑time in the usual algorithmic model, and appending is amortised constant time. Map lookup, insertion, and deletion are conventionally treated as average constant‑time hash operations for this solution. Under those assumptions, each public method meets the exercise's average O(1) target, and storage is O(n) for n current values.

There is a language‑level qualification worth keeping. The ECMAScript Map specification requires average access times that are sublinear in collection size, rather than prescribing a hash table with an exact O(1) guarantee. Our complexity argument uses the normal hash‑map cost model; it isn't a universal promise about every possible JavaScript implementation.

Replacing the map with a linear array search would make removal and membership linear. Rebuilding an array from a set inside getRandom would likewise make every sample linear. Both versions can produce correct small examples, which is why checking only returned values does not establish the requested complexity.


Equal Positions and Imperfect Randomness

MDN's documentation for Math.random describes a pseudorandom value from zero inclusive to one exclusive, with an approximately uniform distribution. Multiplying by the array length and flooring maps that interval into equally sized index intervals in the idealised continuous model.

Math.round is the wrong operation here. Rounding gives the outer indices different interval widths, and multiplying by the full length can also produce an out‑of‑range index. Flooring keeps the conventional mapping aligned with valid array positions.

This implementation is appropriate for the exercise's ordinary random sampling. It is not a cryptographic draw or a promise of exact uniformity across all finite floating‑point generator states. If a product needs auditable selection probabilities or security‑sensitive unpredictability, choosing and specifying the generator becomes a separate requirement. The dense‑array representation still helps, but it doesn't settle that policy.


Test the Structure Without Relying on Luck

A test that calls getRandom twice and expects different values is wrong: repetition is allowed. A frequency test can detect a gross bias over many trials, but it is probabilistic and doesn't prove the mapping or the representation correct.

For deterministic structural checks, temporarily replace Math.random in an isolated test with values selecting the middle of each index interval. After a sequence of inserts and removals, enumerate those choices and compare the returned values with an independent reference set. Restore the original function afterwards so the test doesn't leak into unrelated code.

I include duplicate insertion, absent removal, removal of the final value, repeated removal to empty, and reinsertion after emptying. Testing index zero is particularly useful because a truthiness check on the looked‑up index would incorrectly report the first value as absent. The explicit undefined comparison avoids that mistake.

My circular queue article also separates the logical collection from its physical positions, though its ordering requirements are different. My streaming heap article uses controlled reordering for another purpose. Here, giving up order buys us a cheap deletion. I would make that trade explicit in any reusable interface: callers must not start relying on an order the data structure is free to rearrange.


Planning a platform change?

I help teams make difficult platform work clearer, from architecture decisions and migrations to launch recovery, performance, and search visibility.