# Valid Triangle Number

• Solution#2 in python can not pass.

• 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.

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

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

• me too, I tried it many times.

• @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).

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

• @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

``````

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

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