Valid Triangle Number


  • 0

    Click here to see the full article post


  • 0
    T

    Solution#2 in python can not pass.


  • 0

    @tangweiqiang Could you please share your python solution here?


  • 0
    T

    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
    

  • 0

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


  • 0
    V

    Yea, my Python solution was always showing up as TLE. I tried two different approaches during the contest.


  • 0
    A

    Approach 2, 4th Para: (k-1) + (j+1) + 1 should be (k-1) - (j+1) + 1


  • 0
    J

    me too, I tried it many times.


  • 0

    @aayushgarg Corrected now. Thanks for pointing out.


  • 0

    Could you tell me why you did not use the iterative binary search approach that does not take extra space in Solution#2?


  • 0

    @Yueyi-Wang Thanks for your suggestion. I have converted #2 approach into an iterative version.


  • 0
    L

    For approach 2, it says : Space complexity : O(logn). Sorting takes O(logn) space.
    Shouldn't that be O(1).


  • 0

    @l3arner Java Arrays.sort uses dual pivot quick sort algorithm. You can check its implementation here.


  • 0
    L

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


  • 0

    @l3arner Thanks for pointing out. I have corrected it.


  • 1
    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 += (k-1) - j
        return result
            
    

  • 0
    L

    In the Approach Two Paragraph 2 and 3, all the nums[k] > nums[i] + nums[j] should be nums[k] < nums[i] + nums[j]


Log in to reply
 

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