Tags: "leetcode", "two-pointers", access_time 1-min read

Valid Triangle Number

Created: August 25, 2019 by [lek-tin]

Last updated: August 25, 2019

Given an array consists of non-negative integers, your task is to count 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: [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

Note

1. The length of the given array won’t exceed 1000.
2. The integers in the given array are in the range of [0, 1000].

Solution

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        # a + b < c
        # 0 < a, b, c
        if not nums or len(nums) < 3:
            return 0

        nums.sort(reverse=True)
        count = 0

        for i in range(len(nums)-2):
            c = nums[i]
            left, right = i+1, len(nums)-1
            while left < right:
                a, b = nums[left], nums[right]
                if a + b > c:
                    count += right - left
                    left += 1
                else:
                    right -= 1

        return count