Problem URL: Valid triangle number

We will sort the array. We will iterate over the array and use two pointers to find the number of valid triangles. We will return the result.

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        res = 0
        for i in range(len(nums)-1, 1, -1):
            l, r = 0, i-1
            while l < r:
                if nums[l] + nums[r] > nums[i]:
                    res += r - l
                    r -= 1
                else:
                    l += 1
        return res

Time complexity: O(n^2)
Space complexity: O(1)