The trick here is to name the state correctly, then let the implementation follow. For 295. Find Median from Data Stream, 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, heap / priority queue, binary search, greedy.
The notes already sitting in the source point us in the right direction:
- Approach 1: Simple Sorting
- TLE
- 15 / 18 test cases passed.
- time: O(NlogN), space: O(N)
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 addNum, findMedian.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The heap keeps the best candidate available without sorting the whole world every time.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
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+logN) = O(N), space: O(N)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Approach 1: Simple Sorting
02//TLE
03//15 / 18 test cases passed.
04//time: O(NlogN), space: O(N)
05class MedianFinder {
06public:
07 vector<int> vec;
08 /** initialize your data structure here. */
09 MedianFinder() {
10
11 }
12
13 void addNum(int num) {
14 vec.push_back(num);
15 sort(vec.begin(), vec.end());
16 }
17
18 double findMedian() {
19 int n = vec.size();
20 if(n&1) return vec[n>>1];
21 return (vec[(n>>1)-1]+vec[n>>1])/2.0;
22 }
23};
24
25/**
26 * Your MedianFinder object will be instantiated and called as such:
27 * MedianFinder* obj = new MedianFinder();
28 * obj->addNum(num);
29 * double param_2 = obj->findMedian();
30 */
31
32//Approach 2: Insertion Sort
33//Runtime: 444 ms, faster than 15.81% of C++ online submissions for Find Median from Data Stream.
34//Memory Usage: 46.8 MB, less than 94.97% of C++ online submissions for Find Median from Data Stream.
35//time: O(N+logN) = O(N), space: O(N)
36class MedianFinder {
37public:
38 vector<int> vec;
39 /** initialize your data structure here. */
40 MedianFinder() {
41
42 }
43
44 void addNum(int num) {
45 if(vec.empty()){
46 vec.push_back(num);
47 }else{
48 /*
49 lower_bound: find the smallest number >= x
50 if there is no such element, it returns vec.end(),
51 in this case, this statement is still safe
52 */
53 vec.insert(lower_bound(vec.begin(), vec.end(), num), num);
54 }
55 }
56
57 double findMedian() {
58 int n = vec.size();
59 if(n&1) return vec[n>>1];
60 return (vec[(n>>1)-1]+vec[n>>1])/2.0;
61 }
62};
63
64//Approach 3: Two Heaps
65//Runtime: 424 ms, faster than 18.81% of C++ online submissions for Find Median from Data Stream.
66//Memory Usage: 47 MB, less than 41.77% of C++ online submissions for Find Median from Data Stream.
67//time: O(logN), space: O(N)
68class MedianFinder {
69public:
70 //maxPQ: smaller half, may contain one more element than minPQ
71 //minPQ: larger half
72 priority_queue<int, vector<int>> maxPQ;
73 priority_queue<int, vector<int>, greater<int>> minPQ;
74
75 /** initialize your data structure here. */
76 MedianFinder() {
77
78 }
79
80 void addNum(int num) {
81 maxPQ.push(num);
82 int t = maxPQ.top(); maxPQ.pop();
83 minPQ.push(t);
84
85 //minPQ's size must be <= maxPQ's size
86 if(minPQ.size() > maxPQ.size()){
87 t = minPQ.top(); minPQ.pop();
88 maxPQ.push(t);
89 }
90 }
91
92 double findMedian() {
93 if(maxPQ.size() > minPQ.size()){
94 return maxPQ.top();
95 }
96 return (maxPQ.top()+minPQ.top())/2.0;
97 }
98};
99
100//Approach 4: Multiset and Two Pointers
101//Runtime: 220 ms, faster than 95.39% of C++ online submissions for Find Median from Data Stream.
102//Memory Usage: 49.3 MB, less than 9.29% of C++ online submissions for Find Median from Data Stream.
103//time: O(logN), space: O(N)
104class MedianFinder {
105public:
106 //AVL tree
107 multiset<int> mset;
108 multiset<int>::iterator lo, hi;
109
110 /** initialize your data structure here. */
111 MedianFinder() {
112
113 }
114
115 void addNum(int num) {
116 int n = mset.size();
117 multiset<int>::iterator it = mset.insert(num);
118
119 if(!n){
120 //originally empty
121 lo = hi = it;
122 }else if(n&1){
123 //odd number of elements, lo and hi points to same location
124 if(num < *lo){
125 /*
126 [1,2,3]
127 becomes
128 [1,1,2,3]
129 */
130 --lo;
131 }else if(num == *lo){
132 /*
133 In C++, if there are already elements equal to num,
134 then it insert num after such elements,
135 so larger half's size will increase
136
137 [1,2,3]: lo and hi points to 2
138 becomes
139 [1,2,2,3]: lo points to 1st 2, hi points to 2nd 2
140 */
141 ++hi;
142 }else{
143 //num > *lo
144 ++hi;
145 }
146 }else{
147 //even number of elements
148 if(*lo <= num && num < *hi){
149 //note the <= and < here!!
150 /*
151 In C++, if there are already elements equal to num,
152 then it insert num after such elements
153
154 so when num equal to *lo,
155 it will also be inserted btw the two pointers
156 */
157 lo = hi = it;
158 }else if(num < *lo){
159 /*
160 only when num < *lo(not ==),
161 num is inserted before lo
162
163 [1,3,4,5]
164 becomes
165 [1,2,3,4,5]
166 */
167 hi = lo;
168 //lo and hi both points to old lo
169 }else{
170 /*
171 when num >= *hi,
172 num is always inserted after hi
173
174 [1,3,4,5]
175 becomes
176 [1,3,4,5,6]
177 */
178 lo = hi;
179 //lo and hi both points to old hi
180 }
181 }
182 }
183
184 double findMedian() {
185 return (*lo + *hi)/2.0;
186 }
187};
188
189//Multiset and One Pointer
190//Runtime: 300 ms, faster than 44.92% of C++ online submissions for Find Median from Data Stream.
191//Memory Usage: 49.5 MB, less than 5.62% of C++ online submissions for Find Median from Data Stream.
192class MedianFinder {
193public:
194 multiset<int> mset;
195 //mid points to the lower median if mset have even elements
196 multiset<int>::iterator mid;
197
198 /** initialize your data structure here. */
199 MedianFinder() {
200
201 }
202
203 void addNum(int num) {
204 int n = mset.size();
205 mset.insert(num);
206
207 if(n == 0){
208 mid = mset.begin();
209 }else if(num < *mid){
210 /*
211 [1,3,4]
212 becomes
213 [1,2,3,4]
214
215 [1,3,4,5]
216 beocmes
217 [1,2,3,4,5]
218 */
219 mid = (n&1) ? prev(mid) : mid;
220 }else{
221 //num >= *mid, num is inserted after mid
222 /*
223 [1,3,4]
224 becomes
225 [1,3,4,6]
226
227 [1,3,4,5]
228 beocmes
229 [1,3,4,5,6]
230 */
231 mid = (n&1) ? mid : next(mid);
232 }
233 }
234
235 double findMedian() {
236 int n = mset.size();
237 return (n&1) ? *mid: (*mid + *(next(mid)))/2.0;
238 }
239};Cost
Complexity
Time
O(N+logN) = O(N), space: O(N)
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.