Valid Triangle Number



Sure.
from bisect import bisect_left def find_lt(a, x): i = bisect_left(a, x) return i  1 class Solution(object): def triangleNumber(self, nums): if len(nums) < 3: return 0 nums.sort() c = 0 for i in range(len(nums)): for j in range(i + 1, len(nums)): ab = nums[i] + nums[j] offset = find_lt(nums[j+1:], ab) if offset != 1: c += offset+1 return c

@tangweiqiang Not sure why this approach in python is TLE. Maybe #3 approach is expected.


@vinod23 Thanks Vinod. I am not that familiar with Java but the reason I pointed out as you still do sorting for the 3rd case but it says: "Space complexity : O(1) Constant space is used."


class Solution(object): # This is a slightly different binary search # When all the elements are equal to the target, it always return the left most element # If target is not found, it will return the index of element just larger than target # Have to take care of the edge case if the target is larger than last element # For exmaple, Find 3 # 1 1 1 2 2 4 4 # l m r # l m r # l r # def binarySearch(self, nums, l, r, target): while l < r: mid = (l+r) / 2; if nums[mid] >= target: r = mid; else: l = mid + 1; return l if target <= nums[l] else l+1 # This algorithm will give us O(n^2logn) time complexity. def triangleNumber(self, nums): nums.sort() result = 0 for i in range(len(nums)2): for j in range(i+1, len(nums)1): k = self.binarySearch(nums, j+1, len(nums)1, nums[i]+nums[j]) result += (k1)  j return result