short but slow Python with bisect


  • 1

    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

  • 0

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


  • 0

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


  • 0

    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.


  • 0

    @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?


  • 0

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


  • 0

    @lee215 said in short but slow Python with bisect:

    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.


  • 0

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


  • 0
    G

    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
    ``

  • 0
    D

    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;
        }
    

Log in to reply
 

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