Saved from https://leetcode.com/problems/valid-triangle-number/

lc611

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        """
        Idea: a variant of 3-sum where two pointers need to be in the same side
        Time: O(n^2)
        Space: O(1)
        Requirement of a valid triangle: the smaller two numbers must greater than the biggest number in the triplet
        """
        nums.sort()
        n = len(nums)
        count = 0
        for start in range(n - 2):
            l, r = start + 1, start + 2
            while r < n:
                if nums[start] + nums[l] > nums[r]:
                    count += r - l
                    r += 1
                elif l < r:
                    l += 1
                else:
                    r += 1
                    
        return count