Binary Search part 2

611. Valid Triangle Number

https://leetcode.com/problems/valid-triangle-number/

Naive O(n³) will get TLE

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums = [n for n in nums if n]
        nums.sort()
        res = 0
        for i in range(len(nums)-2):
            for j in range(i+1,len(nums)-1):
                this_s = nums[i]+nums[j]
                for k in range(j+1, len(nums)):
                    if nums[k]<this_s:
                        res+=1
                    else:
                        break
        return res

Binary works with the time complexity of O(n²logn)

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums = [n for n in nums if n]
        nums.sort()
        res = 0
        def good(m, s):
            return s>nums[m]
        def binary(i, s):
            l, r =i, len(nums)-1
            if not good(l,s):return i-1
            while l<r:
                m = (l+r+1)//2
                if good(m, s):
                    l = m
                else:
                    r = m-1
            return l
        for i in range(len(nums)-2):
            for j in range(i+1,len(nums)-1):
                this_s = nums[i]+nums[j]
                k = binary(j+1, this_s)
                res += k-j
                #for k in range(j+1, len(nums)):  
        return res

We can have a faster O(n²) algorithm

class Solution(object):
    def triangleNumber(self, nums):
        nums, count, n = sorted(nums, reverse=True), 0, len(nums)
        for i in range(n):
            j, k = i + 1, n - 1
            while j < k:
                # any value x between j...k will satisfy nums[j] + nums[x] > nums[i]
                # and because nums[i] > nums[j] > nums[x] >= 0, they will always satisfy
                # nums[i] + nums[x] > nums[j] and nums[i] + nums[j] > nums[x]
                if nums[j] + nums[k] > nums[i]:
                    count += k - j
                    j += 1
                else:
                    k -= 1
        return count

I suppose the code below will have a complexity sub O(n²), however, the runtime is slower than the previous one.

class Solution(object):
    def triangleNumber(self, nums):
        nums.sort(reverse = True)
        count, n = 0, len(nums)
        self.operations = 0
        def good(i,j, k):
            return nums[j]+nums[k]>nums[i]
        def binary(i,j, k):
            if nums[j]+nums[j+1]<=nums[i]:return 0
            lo, hi = j+1, k
            while lo<hi:
                self.operations += 1
                mid = (lo+hi+1)//2
                #print('lo,hi',lo, hi, mid)
                if nums[j]+nums[mid]>nums[i]:lo = mid
                else: hi = mid-1
            return lo
            
        for i in range(n):
            k  = n-1
            for j in range(i+1, n-1):
                #print('i,j',i, j)
                k = binary(i, j, k)
                #print('i,j,k',i, j, k, k-j)
                if k==0:break
                count+= k -j
        print(self.operations)
        return count