## Algorithm

Problem Name: 380. Insert Delete GetRandom O(1)

Implement the RandomizedSet class:

• RandomizedSet() Initializes the RandomizedSet object.
• bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
• bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
• int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints:

• -231 <= val <= 231 - 1
• At most 2 * 105 calls will be made to insert, remove, and getRandom.
• There will be at least one element in the data structure when getRandom is called.

## Code Examples

### #1 Code Example with C Programming

Code - C Programming

struct item {
int val;
};
​
#define HASHSZ 100
#define HASHCODE(V) (((unsigned int)V) % HASHSZ)
​
typedef struct {
struct item *items[HASHSZ];
int num;
} RandomizedSet;
​
/** Initialize your data structure here. */
RandomizedSet* randomizedSetCreate() {
RandomizedSet *obj = calloc(1, sizeof(RandomizedSet));
return obj;
}
​
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool randomizedSetInsert(RandomizedSet* obj, int val) {
struct item *e = obj->items[HASHCODE(val)];
while (e && e->val != val) {
}
if (e) {
return false;
}

e = malloc(sizeof(struct item));
//assert(e);
e->val = val;
obj->items[HASHCODE(val)] = e;
obj->num ++;
​
return true;
}
​
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool randomizedSetRemove(RandomizedSet* obj, int val) {
struct item **pp = &obj->items[HASHCODE(val)];
struct item *e = *pp;
while (e && e->val != val) {
e = *pp;
}
if (!e) {
return false;
}

obj->num --;
free(e);

return true;
}
​
/** Get a random element from the set. */
int randomizedSetGetRandom(RandomizedSet* obj) {
int num = 0;
int i = 0, j;
struct item *e = NULL;

if (obj->num == 0) return -1;

j = random() % obj->num;
while (!e && i  <  HASHSZ && j >= 0) {
e = obj->items[i];
while (e && j > 0) {
j --;
}
i ++;
}
return e->val;
}
​
void randomizedSetFree(RandomizedSet* obj) {
struct item *e, *n;
int i;
for (i = 0; i  <  HASHSZ; i ++) {
e = obj->items[i];
while (e) {
free(e);
e = n;
}
}
free(obj);
}
Copy The Code &

Input

cmd
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []]

Output

cmd
[null, true, false, true, 2, true, false, 2]

### #2 Code Example with C++ Programming

Code - C++ Programming

class RandomizedSet {
public:
RandomizedSet() {}

bool insert(int val) {
if(m.count(val)) return false;
m[val] = v.size();
v.push_back(val);
return true;
}

bool remove(int val) {
if(!m.count(val)) return false;
int num = v.back();
m[num] = m[val];
v[m[val]] = num;
v.pop_back();
m.erase(val);
return true;
}

int getRandom() {
return v[rand() % v.size()];
}

private:
unordered_map < int, int>m;
vector<int>v;
};
Copy The Code &

Input

cmd
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []]

Output

cmd
[null, true, false, true, 2, true, false, 2]

### #3 Code Example with Java Programming

Code - Java Programming

class RandomizedSet {

private List randomizedSet;
private Map < Integer, Integer> indexMap;
private int currSize;

public RandomizedSet() {
this.randomizedSet = new ArrayList < >();
this.indexMap = new HashMap<>();
this.currSize = 0;
}

public boolean insert(int val) {
if (this.indexMap.containsKey(val)) {
return false;
}
this.indexMap.put(val, this.currSize++);
return true;
}

public boolean remove(int val) {
if (!this.indexMap.containsKey(val)) {
return false;
}
int valIdx = this.indexMap.get(val);
this.indexMap.put(this.randomizedSet.get(this.currSize - 1), valIdx);
this.randomizedSet.set(valIdx, this.randomizedSet.get(this.currSize - 1));
this.randomizedSet.remove(this.currSize - 1);
this.indexMap.remove(val);
this.currSize--;
return true;
}

public int getRandom() {
return this.randomizedSet.get(new Random().nextInt(this.currSize));
}
}
Copy The Code &

Input

cmd
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []]

Output

cmd
[null, true, false, true, 2, true, false, 2]

### #4 Code Example with Javascript Programming

Code - Javascript Programming

const RandomizedSet = function () {
this.arr = []
this.map = new Map()
}

RandomizedSet.prototype.insert = function (val) {
const {arr, map} = this
if(map.has(val)) return false
const size = arr.length
arr.push(val)
map.set(val, size)
return true
}

RandomizedSet.prototype.remove = function (val) {
const {arr, map} = this
if(!map.has(val)) return false
const idx = map.get(val), last = arr[arr.length - 1]
arr[idx] = last
map.set(last, idx)
arr.pop()
map.delete(val)
return true
}

RandomizedSet.prototype.getRandom = function () {
return this.arr[~~(this.arr.length * Math.random())]
}
Copy The Code &

Input

cmd
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []]

Output

cmd
[null, true, false, true, 2, true, false, 2]

### #5 Code Example with Python Programming

Code - Python Programming

class RandomizedSet:

def __init__(self):
"""
"""
self.nums, self.ind = [], {}
def insert(self, val):
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
:type val: int
:rtype: bool
"""
if val not in self.ind:
self.nums += val,
self.ind[val] = len(self.nums) - 1
return True
return False

def remove(self, val):
"""
Removes a value from the set. Returns true if the set contained the specified element.
:type val: int
:rtype: bool
"""
if val in self.ind:
ind, last = self.ind[val], self.nums[-1]
self.nums[ind], self.ind[last] = last, ind
self.nums.pop()
self.ind.pop(val)
return True
return False

def getRandom(self):
"""
Get a random element from the set.
:rtype: int
"""
return random.choice(self.nums)

# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
Copy The Code &

Input

cmd
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []]

Output

cmd
[null, true, false, true, 2, true, false, 2]

### #6 Code Example with C# Programming

Code - C# Programming

using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _0380_InsertDeleteGetRandom
{
private readonly Random random = new Random();
private readonly IDictionary < int, int> locations;

/** Initialize your data structure here. */
public _0380_InsertDeleteGetRandom()
{
locations = new Dictionary < int, int>();
nums = new List<int>();
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public bool Insert(int val)
{
if (locations.ContainsKey(val)) return false;
return true;
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
public bool Remove(int val)
{
if (!locations.ContainsKey(val)) return false;
if (locations[val] != nums.Count - 1)
{
nums[locations[val]] = nums[nums.Count - 1];
locations[nums[nums.Count - 1]] = locations[val];
}

locations.Remove(val);
nums.RemoveAt(nums.Count - 1);
return true;
}

/** Get a random element from the set. */
public int GetRandom()
{
var index = random.Next(nums.Count);
return nums[index];
}
}
}
Copy The Code &

Input

cmd
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []]

Output

cmd
[null, true, false, true, 2, true, false, 2]