Problem description:

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:

1
2
3
4
5
6
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:

1
2
Input: nums = [4,2,3,4]
Output: 4

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

Solution:

Example:

arr = [3, 4, 6, 38, 39 ]

now your low = 3, high = 38, arr[i] = 39

Triangle inequality says that any 2 sides of triangle should be greater than the 3rd side.

you now know that your array is sorted so3 + 38 > 39 [3, 38, 39]and the numbers which would come after 3 would be greater than 3 so next possible sides of triangles would include[4, 38, 39] , [6, 38, 39]. That is why you add the difference ofhigh - low` which is in this case 3 - 0 = 3 possible sides of triangles as shown above.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        res = 0
        nums.sort()
        for i in range(len(nums)-1, 1, -1):
            left, right = 0, i-1
            while left < right:
                if nums[i] < nums[left]+ nums[right]:
                    res += right-left
                    right -= 1
                else:
                    left += 1
        return res

time complexity: $O(n)$
space complexity: $O()$
reference:
related problem: