# Unrolled linked list: 162ms in C++

• We maintain a `list<vector<int>>` which keeps the size of each vector `<2 * N`. Once a new element is added into a vector and its size exceeds `2 * N`, we move half elements in it into a new vector, and insert the new one into the the list.

The performance depends on `N`. The best value is `sqrt(size)` when its complexity reaches `O(sqrt(size))` for both add & query.

For detailed analysis, see Wiki page of Unrolled linked list

An example for N=3

``````// Before
[ [1, 2, 3] ] -> [ [4, 5, 6, 7, 8, 9] ] -> [ [11, 12, 13] ]
[ [1, 2, 3] ] -> [ [4, 5, 6] ] -> [ [7, 8, 9, 10] ] -> [ [11, 12, 13] ]
// Find the median (6th element)
[ [1, 2, 3] ] -> [ [4, 5, 6] ] -> [ [7, 8, 9, 10] ] -> [ [11, 12, 13] ]
^ this block contains [0, 3)-th elements, skip
[ [1, 2, 3] ] -> [ [4, 5, 6] ] -> [ [7, 8, 9, 10] ] -> [ [11, 12, 13] ]
^ this block contains [3, 6)-th elements, skip
[ [1, 2, 3] ] -> [ [4, 5, 6] ] -> [ [7, 8, 9, 10] ] -> [ [11, 12, 13] ]
^ this block contains [6, 10)-th elements, so the 6th element could be v[6 - 6] == v[0] in this block
``````

Code:

``````class MedianFinder {
list<vector<int>> l;
int size = 0;
static const int N = 128;
void insert_v(vector<int> &v, int x)
{
v.resize(v.size() + 1); int i;
for (i = v.size() - 1; i>=1; --i)
if (v[i-1] > x)
v[i] = v[i-1];
else
{
v[i] = x;
break;
}
if (!i) v[0] = x;
}
public:
/** initialize your data structure here. */
MedianFinder() {
l.clear();
size = 0;
}

if (l.empty())
l.push_back(vector<int> {num});
else
for (auto it = l.begin() ; it != l.end(); ++it)
if (next(it) == l.end() || num < *next(it)->begin())
{
insert_v(*it, num);
if (it->size() > 2 * N)
{
vector<int> new_v(it->begin() + N, it->end());
it->resize(N);
l.insert(next(it), std::move(new_v));
}
break;
}
++size;
//  cout << "Added " << num << endl;
}

double findMedian() {
int cnt = 0;
int sum = 0; /*
for (auto &&block: l)
{
cout << "Block: "; for(int i: block) cout << i << ",";
cout << " \t";
}
cout << endl; */
for (auto it = l.begin(); it != l.end(); ++it)
{
int r = cnt + it->size();
if (size / 2 >= cnt && size / 2 < r)
sum += (*it)[size / 2 - cnt];
if (size % 2 == 0)
if (size / 2 - 1 >= cnt && size / 2 - 1 < r)
sum += (*it)[size / 2 - 1 - cnt];
cnt = r;
}
//cout << "Found!" << endl;
return size % 2 ? sum : sum / 2.0;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.