# Solution For Valid Triangle Number

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.

## Step by Step Implementation For Valid Triangle Number

//Solution: class Solution { public int triangleNumber(int[] nums) { // sort the array first Arrays.sort(nums); int count = 0; // iterate through the array for (int i = 0; i < nums.length - 2; i++) { int k = i + 2; // start from the element next to the current one for (int j = i + 1; j < nums.length - 1 && nums[i] != 0; j++) { // find the first element that is larger than the sum of the other two while (k < nums.length && nums[i] + nums[j] > nums[k]) { k++; } // the number of valid triangles will be the difference between the current k and the original k count += k - j - 1; } } return count; } }

def validTriangleNumber(nums): # sort the list in ascending order nums.sort() # iterate through the list for i in range(len(nums) - 2): # set left pointer to i + 1 left = i + 1 # set right pointer to the end of the list right = len(nums) - 1 # while the left pointer is less than the right pointer while left < right: # if the sum of the sides at the left and right pointers is greater than the side at the current index if nums[left] + nums[right] > nums[i]: # the number of possible triangles is the difference between the right and left pointers plus 1 # this is because everything between the left and right pointers will satisfy the triangle inequality # since the sides are in ascending order result += right - left # move the left pointer to the right by one left += 1 # otherwise, move the right pointer to the left by one else: right -= 1 return result

/** * @param {number[]} nums * @return {number} */ // Sort the input array nums.sort((a, b) => a - b); // Initialize count to 0 let count = 0; // Iterate over the array from the end for (let i = nums.length - 1; i >= 2; i--) { // Initialize left pointer to i - 1 let left = i - 1; // Initialize right pointer to i - 2 let right = i - 2; // While left pointer is greater than right pointer while (left > right) { // If the sum of the 3 elements at the pointers is greater than 0 if (nums[i] + nums[left] > nums[right]) { // The number of valid triangles that can be formed // with the ith element as the largest element is // the difference between the left and right pointers count += left - right; // Since we know that the ith element can be used to // form a valid triangle with the current left element, // we can move the left pointer one element to the right left--; } // Otherwise, we know that the ith element cannot be used // to form a valid triangle with the current left element, // so we move the right pointer one element to the left else { right--; } } } // Return the count return count;

class Solution { public: int triangleNumber(vector& nums) { // sort the array first sort(nums.begin(), nums.end()); int n = nums.size(); // initialize result int count = 0; // fix the first element. We need to run till n-3 as the other two elements are selected from arr[i+1...n-1] for (int i = 0; i < n-2; ++i) { // initialize other two elements as corner elements of subarray arr[j+1..k] int j = i + 1, k = i + 2; // Use Meet in the Middle concept while (j < k) { // If we find a valid triangle then do 2 things // 1) Increment j to get a different combination // 2) Reduce k to get a different combination // This loop runs till the second last element if (nums[i] + nums[j] > nums[k]) { // This is important. For current i and j, there // can be total k-j third elements. count += (k - j); ++j; } else ++k; } } return count; } };

public class Solution { public int TriangleNumber(int[] nums) { // sort the array first Array.Sort(nums); // for each element in the array, // check if there are two other elements // that can form a valid triangle with it int count = 0; for (int i = 0; i < nums.Length; i++) { int j = 0; int k = i - 1; while (j < k) { // if the sum of the two elements is greater // than the current element, then we know // that the current element can form a valid // triangle with the two other elements if (nums[j] + nums[k] > nums[i]) { // since the array is sorted, we know that // all the elements between j and k can form // a valid triangle with the current element // so we can just add k - j to our count count += k - j; // move k down to the next element k--; } // otherwise, we know that the current element // can't form a valid triangle with the two other // elements, so we move j up to the next element else { j++; } } } return count; } }