Problem statement

https://binarysearch.com/problems/Triangle-Triplets/

Solution

Equal to Leetcode 0611. Valid Triangle Number.

Complexity

Time complexity is O(n^2), space complexity is O(1).

Code

class Solution:
    def solve(self, nums):
        nums, count, n = sorted(nums), 0, len(nums)
        for i in range(2, n):
            left, right = 0, i-1
            while left < right:
                if nums[left] + nums[right] > nums[i]:
                    count += (right - left)
                    right -= 1
                else:
                    left += 1
        return count