# LeetCode 380: Insert Delete GetRandom O(1)

## Problem Restatement

We need to implement a data structure called `RandomizedSet`.

It supports three operations:

| Operation | Meaning |
|---|---|
| `insert(val)` | Insert `val` if it does not already exist |
| `remove(val)` | Remove `val` if it exists |
| `getRandom()` | Return a random element from the current set |

Each operation must run in average `O(1)` time.

For `getRandom()`, every element currently in the set must have the same probability of being returned. The problem guarantees that `getRandom()` is only called when the set has at least one element. The constraints allow at most `2 * 10^5` calls, and values fit in signed 32-bit integer range.

## Input and Output

| Method | Input | Output |
|---|---|---|
| `RandomizedSet()` | None | Initializes the data structure |
| `insert(val)` | Integer `val` | `True` if inserted, `False` if already present |
| `remove(val)` | Integer `val` | `True` if removed, `False` if absent |
| `getRandom()` | None | A uniformly random current element |

Example class shape:

```python
class RandomizedSet:

    def __init__(self):
        ...

    def insert(self, val: int) -> bool:
        ...

    def remove(self, val: int) -> bool:
        ...

    def getRandom(self) -> int:
        ...
```

## Examples

Example:

```python
randomizedSet = RandomizedSet()
```

Insert `1`:

```python
randomizedSet.insert(1)
```

This returns:

```python
True
```

because `1` was not already present.

Remove `2`:

```python
randomizedSet.remove(2)
```

This returns:

```python
False
```

because `2` does not exist.

Insert `2`:

```python
randomizedSet.insert(2)
```

This returns:

```python
True
```

Now the set contains:

```python
{1, 2}
```

Call:

```python
randomizedSet.getRandom()
```

This should return either `1` or `2`, each with probability `1 / 2`.

Remove `1`:

```python
randomizedSet.remove(1)
```

This returns:

```python
True
```

Now the set contains only:

```python
{2}
```

Insert `2` again:

```python
randomizedSet.insert(2)
```

This returns:

```python
False
```

because `2` is already present.

Now:

```python
randomizedSet.getRandom()
```

must return:

```python
2
```

## First Thought: Use a Hash Set

A hash set gives fast insert and remove.

```python
values = set()
```

Then:

```python
insert(val) -> O(1) average
remove(val) -> O(1) average
```

But `getRandom()` is the problem.

A hash set does not support direct random indexing. To choose a random element uniformly, we would need to convert it to a list or iterate through it, which costs `O(n)`.

So a hash set alone is not enough.

## Key Insight

We need two abilities at the same time:

| Need | Good structure |
|---|---|
| Check whether a value exists | Hash map |
| Pick a random element by index | Array |

An array lets us do this in `O(1)`:

```python
values[random_index]
```

A hash map lets us find the position of a value in `O(1)` average time:

```python
index[val]
```

So we store both:

| Structure | Meaning |
|---|---|
| `values` | List of all current values |
| `pos` | Map from value to its index in `values` |

The only hard part is removal.

Removing from the middle of a Python list costs `O(n)` because elements after it must shift left.

To avoid that, we use swap and pop.

## Swap and Pop Removal

Suppose the list is:

```python
values = [10, 20, 30, 40]
```

and we want to remove `20`.

The index of `20` is `1`.

Removing directly from index `1` would shift `30` and `40`.

Instead:

1. Move the last value `40` into index `1`.
2. Update `pos[40]` to `1`.
3. Pop the last element.

The list changes like this:

```python
[10, 20, 30, 40]
[10, 40, 30, 40]
[10, 40, 30]
```

Now `20` is gone, and we removed from the end of the list.

Popping from the end is `O(1)`.

## Algorithm

Initialize:

```python
values = []
pos = {}
```

For `insert(val)`:

1. If `val` exists in `pos`, return `False`.
2. Store its index as the current list length.
3. Append `val` to `values`.
4. Return `True`.

For `remove(val)`:

1. If `val` does not exist in `pos`, return `False`.
2. Get its index.
3. Get the last value in `values`.
4. Move the last value into the removed value's index.
5. Update the last value's index in `pos`.
6. Pop the last list element.
7. Delete `val` from `pos`.
8. Return `True`.

For `getRandom()`:

1. Choose a random element from `values`.
2. Return it.

## Correctness

The list `values` stores exactly the elements currently in the set.

The map `pos` stores the current index of every value in `values`.

When `insert(val)` succeeds, `val` was not present before. The algorithm appends it to `values` and records its index in `pos`, so both structures remain consistent.

When `insert(val)` fails, `val` already exists, so leaving the structures unchanged is correct.

When `remove(val)` fails, `val` is absent, so leaving the structures unchanged is correct.

When `remove(val)` succeeds, the algorithm removes exactly `val`. If `val` is not already the last element, the last element is moved into `val`'s old position, and its index is updated in `pos`. Then the duplicate last slot is popped. Finally, `val` is removed from `pos`.

After this process, all remaining values still appear exactly once in `values`, and every value has the correct index in `pos`.

`getRandom()` chooses uniformly from the list `values`. Since each current set element appears exactly once in `values`, every element has equal probability of being returned.

Therefore all operations satisfy the required behavior.

## Complexity

Let `n` be the number of current elements.

| Operation | Time | Why |
|---|---|---|
| `insert(val)` | `O(1)` average | Hash map lookup and list append |
| `remove(val)` | `O(1)` average | Hash map lookup, swap, pop |
| `getRandom()` | `O(1)` | Random list access |
| Space | `O(n)` | Store each value in the list and map |

## Implementation

```python
import random

class RandomizedSet:

    def __init__(self):
        self.values = []
        self.pos = {}

    def insert(self, val: int) -> bool:
        if val in self.pos:
            return False

        self.pos[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.pos:
            return False

        idx = self.pos[val]
        last = self.values[-1]

        self.values[idx] = last
        self.pos[last] = idx

        self.values.pop()
        del self.pos[val]

        return True

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

## Code Explanation

The constructor creates the two structures:

```python
self.values = []
self.pos = {}
```

`self.values` supports random access.

`self.pos` maps each value to its index inside `self.values`.

For insertion, we first reject duplicates:

```python
if val in self.pos:
    return False
```

Then we record the index and append the value:

```python
self.pos[val] = len(self.values)
self.values.append(val)
```

For removal, we first reject missing values:

```python
if val not in self.pos:
    return False
```

Then we find the index of the value being removed:

```python
idx = self.pos[val]
```

We also read the last value:

```python
last = self.values[-1]
```

Move the last value into the removed value's slot:

```python
self.values[idx] = last
self.pos[last] = idx
```

Then remove the old last slot and delete `val` from the map:

```python
self.values.pop()
del self.pos[val]
```

This also works when `val` is already the last value. In that case, the assignment writes the value to the same place, then the pop removes it, then the map entry is deleted.

For random selection:

```python
return random.choice(self.values)
```

Since each value appears once in the list, the probability is uniform.

## Testing

```python
def test_randomized_set():
    rs = RandomizedSet()

    assert rs.insert(1) is True
    assert rs.remove(2) is False
    assert rs.insert(2) is True

    assert rs.getRandom() in {1, 2}

    assert rs.remove(1) is True
    assert rs.insert(2) is False
    assert rs.getRandom() == 2

    assert rs.remove(2) is True
    assert rs.insert(-10) is True
    assert rs.insert(100) is True

    assert rs.remove(-10) is True
    assert rs.getRandom() == 100

    print("all tests passed")

test_randomized_set()
```

Test meaning:

| Test | Why |
|---|---|
| Insert new value | Should return `True` |
| Remove missing value | Should return `False` |
| Insert duplicate | Should return `False` |
| `getRandom()` with two values | Must return one current value |
| Remove one value | Remaining value should still work |
| Remove last value | Checks swap and pop when removing the end |
| Negative value | Confirms full integer range behavior |