DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

Valid Triangle Number

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
Enter fullscreen mode Exit fullscreen mode

Top comments (0)