# 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;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]