Insert Delete GetRandom O(1)

87.9k
0

Implement the RandomizedSet class with the following operations:

  • RandomizedSet() initializes an empty set.

  • insert(int val) inserts val when no equal value already exists. Return true after successful insertion and false when val is already present.

  • remove(int val) removes val when present. Return true after successful removal and false when val is absent.

  • getRandom() returns one currently stored value. Every stored value must have an equal probability of selection.

A getRandom() call always occurs when the set contains at least one value.

Every operation must run in average O(1) time.

Example 1

Input: operations = ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]

Arguments: [[], [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.

  • randomizedSet.remove(2); // Returns false as 2 does not exist.

  • 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, it will always return 2.

Brute Force Approach

A dynamic array supports direct indexed access. Selecting a uniformly random index therefore gives constant-time random retrieval.

Set operations create the difficulty. Duplicate prevention requires searching the array before insertion. Removal also requires locating the value, followed by shifting later values when deletion happens before the final position. Random selection remains efficient, but insertion and removal fail the required average O(1) bound.

Algorithm

  • Initialize an empty dynamic array values to store all distinct values.

For insert(val):

  • Traverse values and compare every stored value with val.

  • Return false after finding an equal value, because duplicate entries are not allowed.

  • Append val at the end after completing the search without a match.

  • Return true after successful insertion.

For remove(val):

  • Traverse values to locate val.

  • Delete the matching position after discovery.

  • Shift every later value one position toward the left through dynamic-array deletion.

  • Return true after successful removal.

  • Return false when the complete array contains no matching value.

For getRandom():

  • Generate a uniformly distributed random index from 0 to values.size() - 1.

  • Return the value stored at the generated index.

Dry Run

j

j

Solution

#include <bits/stdc++.h>
using namespace std;
class RandomizedSet {
private:
vector<int> values;
mt19937 generator;
public:
/* Initializes an empty array-based set. */
RandomizedSet()
: generator(random_device{}()) {
}
/* Inserts val after a linear duplicate check. */
bool insert(int val) {
// Search for an existing occurrence.
for (int value : values) {
if (value == val) {
return false;
}
}
// Append a new distinct value.
values.push_back(val);
return true;
}
/* Removes val through linear search and shifting. */
bool remove(int val) {
// Locate the value inside the array.
for (
int index = 0;
index < (int)values.size();
index++
) {
if (values[index] == val) {
// Erase shifts all later values left.
values.erase(
values.begin() + index
);
return true;
}
}
return false;
}
/* Returns a uniformly selected stored value. */
int getRandom() {
uniform_int_distribution<int> distribution(
0,
(int)values.size() - 1
);
int randomIndex =
distribution(generator);
return values[randomIndex];
}
};
// Driver code to execute the design.
int main() {
RandomizedSet randomizedSet;
cout << boolalpha;
cout << randomizedSet.insert(1) << endl;
cout << randomizedSet.remove(2) << endl;
cout << randomizedSet.insert(2) << endl;
cout << randomizedSet.getRandom() << endl;
cout << randomizedSet.remove(1) << endl;
cout << randomizedSet.insert(2) << endl;
cout << randomizedSet.getRandom() << endl;
return 0;
}

Complexity Analysis

Let N represent the number of currently stored values.

Time Complexity:

  • insert: O(N), because duplicate detection can scan the complete array.

  • remove: O(N), because value search and later-element shifting can both require linear work.

  • getRandom: O(1), because random index generation and array access require constant time.

Space Complexity: O(N), because the dynamic array stores every distinct value once. The random-number generator requires constant additional space.

Better Approach

A HashSet directly handles uniqueness, insertion, lookup, and deletion in average constant time. Duplicate checks no longer require an array traversal.

A HashSet does not support indexed access. Uniform random selection can choose a position from 0 to N - 1, but reaching that position requires iterator movement through the set. HashSet storage improves insertion and removal, while getRandom() still requires linear time.

Algorithm

  • Initialize an empty HashSet values.

For insert(val):

  • Search for val through the HashSet operation.

  • Return false when val already exists.

  • Insert val and return true when no existing entry matches.

For remove(val):

  • Remove val through the HashSet operation.

  • Return true when a stored entry is removed.

  • Return false when val is absent.

For getRandom():

  • Generate a uniformly distributed position from 0 to values.size() - 1.

  • Start from the beginning of the HashSet iterator.

  • Advance until the generated position is reached.

  • Return the value at the selected iterator position.

Dry Run

k

k

Solution

#include <bits/stdc++.h>
using namespace std;
class RandomizedSet {
private:
unordered_set<int> values;
mt19937 generator;
public:
/* Initializes an empty hash-set-based design. */
RandomizedSet()
: generator(random_device{}()) {
}
/* Inserts val through average constant-time hashing. */
bool insert(int val) {
return values.insert(val).second;
}
/* Removes val through average constant-time hashing. */
bool remove(int val) {
return values.erase(val) > 0;
}
/* Returns a random value after linear iterator movement. */
int getRandom() {
uniform_int_distribution<size_t> distribution(
0,
values.size() - 1
);
size_t randomPosition =
distribution(generator);
auto iterator = values.begin();
// Move to the uniformly selected position.
advance(iterator, randomPosition);
return *iterator;
}
};
// Driver code to execute the design.
int main() {
RandomizedSet randomizedSet;
cout << boolalpha;
cout << randomizedSet.insert(1) << endl;
cout << randomizedSet.remove(2) << endl;
cout << randomizedSet.insert(2) << endl;
cout << randomizedSet.getRandom() << endl;
cout << randomizedSet.remove(1) << endl;
cout << randomizedSet.insert(2) << endl;
cout << randomizedSet.getRandom() << endl;
return 0;
}

Complexity Analysis

Let N represent the number of currently stored values.

Time Complexity:

  • insert: Average O(1) through HashSet insertion; worst-case O(N) under severe hash collisions.

  • remove: Average O(1) through HashSet deletion; worst-case O(N) under severe hash collisions.

  • getRandom: O(N) in the worst case, because the iterator may advance through the complete set before reaching the selected position.

Space Complexity: O(N), because the HashSet stores every distinct value once. Random selection uses only constant auxiliary storage beyond the set.

Optimal Approach

The first two approaches each solve only part of the requirement:

  • A dynamic array provides constant-time indexed random access.

  • A HashMap provides average constant-time value lookup.

Combining both structures provides the required operations. The dynamic array stores all values in consecutive positions. The HashMap associates every value with the corresponding array index.

Middle deletion remains the only obstacle because normal array deletion shifts later elements. Moving the final array value into the target position removes the gap. The moved value receives an updated index inside the HashMap, and the final array position can then be removed in constant time.

Algorithm

  • Initialize:

    • A dynamic array values to provide indexed random access.

    • A HashMap valueToIndex to map every stored value to the corresponding array index.

For insert(val):

  • Search for val inside valueToIndex.

  • Return false when an existing mapping is found.

  • Append val to the end of values.

  • Store valueToIndex[val] = values.size() - 1.

  • Return true.

For remove(val):

  • Search for val inside valueToIndex.

  • Return false when no mapping exists.

  • Read the target index associated with val.

  • Read the final value stored inside values.

  • Overwrite the target position with the final value.

  • Update the final value’s mapping to the target index.

  • Remove the final array position through pop.

  • Delete the mapping associated with val.

  • Return true.

The same steps remain valid when val already occupies the final position. The overwrite becomes a self-assignment, followed by the normal pop and map deletion.

For getRandom():

  • Generate a uniformly distributed index from 0 to values.size() - 1.

  • Return values[randomIndex].

Every stored value occupies exactly one array index. Uniform index selection therefore gives every value probability 1 / N.

Dry Run

kk

kk

Solution

#include <bits/stdc++.h>
using namespace std;
class RandomizedSet {
private:
vector<int> values;
unordered_map<int, int> valueToIndex;
mt19937 generator;
public:
/* Initializes an empty indexed randomized set. */
RandomizedSet()
: generator(random_device{}()) {
}
/* Inserts val when no stored mapping exists. */
bool insert(int val) {
if (
valueToIndex.find(val) !=
valueToIndex.end()
) {
return false;
}
// Store the new value at the array end.
values.push_back(val);
// Record the corresponding array index.
valueToIndex[val] =
(int)values.size() - 1;
return true;
}
/* Removes val with the swap-and-pop technique. */
bool remove(int val) {
auto entry = valueToIndex.find(val);
if (entry == valueToIndex.end()) {
return false;
}
int targetIndex = entry->second;
int lastIndex =
(int)values.size() - 1;
int lastValue = values[lastIndex];
// Move the final value into the removed position.
values[targetIndex] = lastValue;
// Update the moved value's stored index.
valueToIndex[lastValue] = targetIndex;
// Remove the final array position.
values.pop_back();
// Remove the deleted value's mapping.
valueToIndex.erase(val);
return true;
}
/* Returns a uniformly selected stored value. */
int getRandom() {
uniform_int_distribution<int> distribution(
0,
(int)values.size() - 1
);
int randomIndex =
distribution(generator);
return values[randomIndex];
}
};
// Driver code to execute the design.
int main() {
RandomizedSet randomizedSet;
cout << boolalpha;
cout << randomizedSet.insert(1) << endl;
cout << randomizedSet.remove(2) << endl;
cout << randomizedSet.insert(2) << endl;
cout << randomizedSet.getRandom() << endl;
cout << randomizedSet.remove(1) << endl;
cout << randomizedSet.insert(2) << endl;
cout << randomizedSet.getRandom() << endl;
return 0;
}

Complexity Analysis

Let N represent the number of currently stored values.

Time Complexity:

  • insert: Average O(1). HashMap lookup and insertion require average constant time, while dynamic-array append requires amortized constant time.

  • remove: Average O(1). HashMap lookup, array overwrite, index update, final-position removal, and map deletion each require average or amortized constant time.

  • getRandom: O(1), because one random index and one array lookup are required.

Hash collisions can produce O(N) worst-case time for insert or remove, but the required bound concerns average operation time.

Space Complexity: O(N), because the dynamic array stores N values and the HashMap stores N value-index mappings.

FAQs about Insert Delete GetRandom O(1)

1. Why does an array alone fail the average O(1) requirement?

Indexed random access takes O(1) time, but duplicate detection and value search require up to O(N) comparisons. Middle deletion can also shift O(N) values.

2. Why does a HashSet alone fail the requirement?

A HashSet supports average O(1) insertion, lookup, and deletion but does not provide constant-time access by numeric index. Reaching a random iterator position requires linear traversal.

3. Why does the HashMap store array indices?

A value’s array position is required during removal. The stored index allows direct access to the target position without scanning the array.

4. Why is the final array value moved into the removed position?

Normal middle deletion creates a gap and shifts later values. Moving the final value fills the gap immediately, after which final-position removal requires constant time.

5. What happens when the removed value already occupies the last position?

The last value and removed value are equal. The overwrite becomes a self-assignment, the final position is popped, and the removed mapping is deleted. No special branch is required.

6. Why does swap-and-pop change the internal order?

The final value replaces the removed value. Set operations do not require insertion-order preservation, so internal reordering does not affect correctness.

7. Why does every value receive equal probability?

Every value occupies exactly one position inside the packed array. Uniform selection among N indices gives every position and corresponding value probability 1 / N.

8. Can a linked list provide the required operations?

A linked list can delete a known node in constant time, but indexed random access requires traversal. A randomly selected position therefore costs O(N) time.

9. Why is remove only average O(1) rather than strict worst-case O(1)?

HashMap lookup and deletion require average constant time. Severe hash collisions can produce linear-time behaviour in the worst case.

10. Is cryptographically secure randomness required?
No. The problem requires equal selection probability among stored values, not security against prediction. A uniform pseudo-random index generator satisfies the algorithmic requirement.

HashingArraysMaths

Read Similar Blogs

HashingData Structures

Count Distinct Elements

Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 , and 30 . 10 and 20 are present twice but counted once. Therefore, the number of distinct elements is...

76.4k
Arrays

Row wise traversal

tuf-examples-1 Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then second row prints as 4 5 6 . Input: mat = [[10, 20], [30, 40], [50, 60]] Output:...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Comments0