611. Valid Triangle Number

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

Solution

Approach 1: Like 3sum. For each target(longest side), find two smaller sides whose sum > target.

Code (Python)

Approach 1:

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        # Like 3sum. For each target(longest side), find two smaller sides whose sum > target
        nums.sort()
        count = 0
        for longest_index in range(2, len(nums)):
            l, r = 0, longest_index - 1
            while l < r:
                if nums[l] + nums[r] <= nums[longest_index]:
                    l += 1
                else:
                    count += (r - l)
                    r -= 1
        return count

Code (C++)

Approach 1:

Approach 2: