Valid Triangle Number - Leetcode Solution

The problem statement for Valid Triangle Number problem on LeetCode can be stated as follows:

Given an array of positive integers nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

A triangle is valid if it satisfies the following conditions:

The sum of its side lengths is greater than 0. The length of any side is less than or equal to the sum of the other two sides.

Algorithm:

To solve this problem, we can sort the given array in non-decreasing order. We can then loop through the array and fix a value for the first side of the triangle and then use two pointers to find the remaining two sides. For any valid triplet found, we can increment our answer by 1.

The reason this works is that if we fix the first side and look for the other two sides, we only need to check for the condition that the sum of the two remaining sides is greater than the first side. This is because if the sum of the two remaining sides is greater than or equal to the first side, a triangle can be formed using these three sides.

The detailed Python implementation of the algorithm is shown below:

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        count = 0
        
        for i in range(n-2):
            k = i + 2
            for j in range(i+1, n-1):
                if nums[i] == 0:    # Skip if first side is 0
                    continue
                while k < n and nums[i] + nums[j] > nums[k]:
                    k += 1
                count += k - j - 1  # Number of triangles with first side as nums[i] and second side as nums[j]
        
        return count

Time Complexity: O(n^2), where n is the length of the given array. We loop over an array of size n at most n times, so the time complexity is O(n^2).

Space Complexity: O(1). We only use constant extra space.

Overall, the above algorithm is an efficient solution to the Valid Triangle Number problem on LeetCode.

1