Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
Example 1:
Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3
Example 2:
Input: nums = [4,2,3,4]
Output: 4
Constraints:
-
1 <= nums.length <= 1000 -
0 <= nums[i] <= 1000
SOLUTION:
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
ctr = 0
i = 2
while i < n:
a = 0
b = i - 1
while a < b:
if nums[a] + nums[b] > nums[i]:
ctr += (b - a)
b -= 1
else:
a += 1
i += 1
return ctr
Top comments (0)