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

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

  • 0
    C

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


Log in to reply
 

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