# short but slow Python with bisect

• Only O(n^2), but has a decent chance to get accepted (just submitted five times, got 1919ms, TLE, TLE, TLE, 1969ms).

``````def reversePairs(self, nums):
count = 0
done = []
for num in nums:
count += len(done) - bisect.bisect(done, num * 2)
bisect.insort(done, num)
return count``````

• @StefanPochmann That's weird. Aren't the same set of test cases run for each submission regardless of the submitter?

• @babhishek21 Yes. Except sometimes new test cases get added. What's weird?

• What's weird is that the same code gives both TLE and AC on repeated runs. I've never seen that happen. Maybe your solution runs on the cusp.

• @babhishek21
The time limit is about 2000ms for this question and you know that the run time are different each time.
The solution above is correct, when <2000ms it is AC and when >2000ms it is TLE.
Do you think that it makes sense?

• @StefanPochmann
Why using `bisect`is still O(n^2)?
I thought bisect.insort is a function of O(logN)

• I thought bisect.insort is a function of O(logN)

No, and the documentation even mentions it:

Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

• @StefanPochmann
I see. it takes O(log n) to search but O(n) to insert. Because it moves the whole list.

• I spent a whole night writing an AVL Tree for nlog complexity, but why it got TLE just like a normal Tree...

``````class TreeNode(object):

def __init__(self, val):
self.l, self.r, self.val, self.cnt, self.hi = None, None, val, 1, 1

class Solution(object):

def hi(self, root):
return root.hi if root else 0

def insert(self, root, val):

if not root: return TreeNode(val)

if val < root.val: root.l = self.insert(root.l, val)
elif root.val < val: root.cnt += 1; root.r = self.insert(root.r, val)
else: root.cnt += 1; return root

root.hi = max(self.hi(root.l), self.hi(root.r)) + 1
diff = self.hi(root.l) - self.hi(root.r)

if diff > 1:
if self.hi(root.l.l) > self.hi(root.l.r): return self.rotRight(root)
else: root.l = self.rotLeft(root.l); return self.rotRight(root)
elif diff < -1:
if self.hi(root.r.r) > self.hi(root.r.l): return self.rotLeft(root)
else: root.r = self.rotRight(root.r); return self.rotLeft(root)

return root

def rotRight(self, root):
newRoot = root.l
root.l = newRoot.r
newRoot.r = root
root.hi = max(self.hi(root.l), self.hi(root.r)) + 1
newRoot.hi = max(self.hi(newRoot.l), self.hi(newRoot.r)) + 1
newRoot.cnt += root.cnt
return newRoot

def rotLeft(self, root):
newRoot = root.r
root.r = newRoot.l
newRoot.l = root
root.hi = max(self.hi(root.l), self.hi(root.r)) + 1
newRoot.hi = max(self.hi(newRoot.l), self.hi(newRoot.r)) + 1
root.cnt -= newRoot.cnt
return newRoot

def search(self, root, val):
if not root: return 0
return root.cnt + self.search(root.l, val) if val < root.val else self.search(root.r, val)

def reversePairs(self, nums):
res = 0
root = None
for x in nums:
res += self.search(root, 2 * x)
root = self.insert(root, x)
return res
````````

• The insert sort gets accepted marginally. But if using multiset, then it will be TLE.

``````    int reversePairs(vector<int>& nums) {
int res = 0;
vector<long> t;
for (int i = nums.size() - 1; i >= 0; --i) {
auto it = upper_bound(t.begin(), t.end(), nums[i]-1);
int d = distance(t.begin(), it);
res += d;
long nn = (long)nums[i]<<1;
it = lower_bound(t.begin(), t.end(), nn);
t.insert(it, nn);
}
return res;
}
``````

• @dengzhizhang this is because multiset::iterator is a bidirectional iterator rather than random access iterator. Bidirectional iterator only supports incremental and decremental operations and std::distance yields O(n) rather than O(1) time complexity when used to compute two iterators' distance.

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