Click here to see the full article post
@tangweiqiang Could you please share your python solution here?
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.
Yea, my Python solution was always showing up as TLE. I tried two different approaches during the contest.
@aayushgarg Corrected now. Thanks for pointing out.
Could you tell me why you did not use the iterative binary search approach that does not take extra space in Solution#2?
@Yueyi-Wang Thanks for your suggestion. I have converted #2 approach into an iterative version.
For approach 2, it says : Space complexity : O(logn). Sorting takes O(logn) space.
Shouldn't that be O(1).
@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."
@l3arner Thanks for pointing out. I have corrected it.
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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.