Python O(n^2)


  • 1
    class Solution(object):
        def triangleNumber(self, nums):
            nums.sort()
            nums = nums[::-1]
            
            sol = 0
            
            for i in range(len(nums) - 2):
                k = len(nums) - 1
                for j in range(i + 1, k):
                    if j >= k:
                        break
                    diff = nums[i] - nums[j]
                    while nums[k] <= diff and k > j:
                        k -= 1
                    sol += (k - j)
            return sol
    

  • 0
    Z

    it is weired that this code has a record of 35 ms while now it occasionally failed for TLE, ref: https://leetcode.com/submissions/detail/105675904/ and https://leetcode.com/submissions/detail/105675749/

    please paste your submission to check if they increase the test cases, currently there are 243 test cases


  • 0
    Z

    Submission Details
    236 / 243 test cases passed.
    Status: Time Limit Exceeded

    Submitted: 0 minutes ago
    Last executed input: [1,22,7,5,8,1,10,2,13,9,19,13,12,15,24,11,25,8,9,13,6,20,24,24,7,3,2,14,11,1,3,3,16,22,11,15,9,3,10,6,15,5,9,1...

    https://leetcode.com/submissions/detail/105679271/


  • -1

    @zqfan Yes, I find it, after tried several times and got tle. The limit should be increased.


  • 0
    A

    Cleaner version using while loop:

    class Solution(object):
        def triangleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            nums.sort()
            nums = nums[::-1]
            sol = 0
            for i in range(len(nums) - 2):
                j = i + 1
                k = len(nums) - 1
                while j < k:
                    diff = nums[i] - nums[j]
                    while nums[k] <= diff and k > j:
                        k -= 1
                    sol += (k - j)
                    j += 1
            return sol
    

Log in to reply
 

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