Let's make this one less mysterious. For 380. Insert Delete GetRandom O(1), the solution in this repository is mainly a data structure design solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: data structure design.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are insert, remove, getRandom.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 156 ms, faster than 13.19% of C++ online submissions for Insert Delete GetRandom O(1).
02//Memory Usage: 22.8 MB, less than 61.19% of C++ online submissions for Insert Delete GetRandom O(1).
03class RandomizedSet {
04public:
05 set<int> myset;
06
07 /** Initialize your data structure here. */
08 RandomizedSet() {
09
10 }
11
12 /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
13 bool insert(int val) {
14 std::pair<std::set<int>::iterator, bool> result = myset.insert(val);
15 return result.second;
16 }
17
18 /** Removes a value from the set. Returns true if the set contained the specified element. */
19 bool remove(int val) {
20 if(myset.find(val) == myset.end()){
21 return false;
22 }
23 myset.erase(val);
24 return true;
25 }
26
27 /** Get a random element from the set. */
28 int getRandom() {
29 int n = myset.size();
30 set<int>::iterator it = myset.begin();
31 advance(it, rand()%n);
32 return *it;
33 }
34};
35
36/**
37 * Your RandomizedSet object will be instantiated and called as such:
38 * RandomizedSet* obj = new RandomizedSet();
39 * bool param_1 = obj->insert(val);
40 * bool param_2 = obj->remove(val);
41 * int param_3 = obj->getRandom();
42 */
43
44//unordered_map + vector
45//https://leetcode.com/problems/insert-delete-getrandom-o1/discuss/85422/AC-C%2B%2B-Solution.-Unordered_map-%2B-Vector
46//Runtime: 80 ms, faster than 75.07% of C++ online submissions for Insert Delete GetRandom O(1).
47//Memory Usage: 22.8 MB, less than 61.84% of C++ online submissions for Insert Delete GetRandom O(1).
48class RandomizedSet {
49public:
50 vector<int> vals;
51 unordered_map<int, int> val2pos;
52
53 /** Initialize your data structure here. */
54 RandomizedSet() {
55
56 }
57
58 /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
59 bool insert(int val) {
60 if(val2pos.find(val) != val2pos.end()){
61 return false;
62 }
63
64 vals.emplace_back(val);
65 val2pos[val] = vals.size()-1;
66
67 return true;
68 }
69
70 /** Removes a value from the set. Returns true if the set contained the specified element. */
71 bool remove(int val) {
72 if(val2pos.find(val) == val2pos.end()){
73 return false;
74 }
75
76 if(vals.back() == val){
77 vals.pop_back();
78 val2pos.erase(val);
79 }else{
80 int last = vals.back(), newpos = val2pos[val];
81 swap(vals.back(), vals[val2pos[val]]);
82 vals.pop_back();
83 val2pos[last] = newpos;
84 val2pos.erase(val);
85 }
86
87 return true;
88 }
89
90 /** Get a random element from the set. */
91 int getRandom() {
92 return vals[rand()%vals.size()];
93 }
94};
95
96/**
97 * Your RandomizedSet object will be instantiated and called as such:
98 * RandomizedSet* obj = new RandomizedSet();
99 * bool param_1 = obj->insert(val);
100 * bool param_2 = obj->remove(val);
101 * int param_3 = obj->getRandom();
102 */Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.