Why is my python solution so slow?


  • 0
    T
    import heapq
    class Solution(object):
        def triangleNumber(self, nums):
    
            nums = sorted(nums)
    
            ans = 0
            pre = []
            c = 0
            m = None
    
            for i in range(len(nums)-2):
    
                for j in range(i,-1,-1):
                    t = nums[i+1] + nums[j]
    
                    if t> nums[i+2]:
                        c += 1
                        heapq.heappush(pre,t)
    
                        if not m or t<m:
                            m = t
                    else:
                        break
    
                flag = 0
                while m and pre and m <= nums[i+2]:
                    m = heapq.heappop(pre)
                    c -= 1
                    flag = 1
                if flag and m>nums[i+2]:
                    heapq.heappush(pre,m)
                    c+=1
    
                ans += c
            return ans
    

    I thought this one is better than O(n^2), but apparently not


Log in to reply
 

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