# Leetcode Question Valid Triangle Number

**Problem Link**\-

[Valid triangle number](https://leetcode.com/problems/valid-triangle-number/)

Problem Statement :

**Problem explanation**: In this problem, we are given an integer array,each element represents length and we need to find all possible triplets that can form a triangle.

**Approach** - For a triangle to form the sum of two sides must be greater than the third side. So we traverse the array and find possible triplets that satisfy this condition.

### Brute Force Approach -

Time Complexity - O(N^3)

Space Complexity - O(1)

In this approach, we will run three loops and check whether two length sum is greater than the third length or not, if yes, then we increase the count variable.

```cpp
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        
        int n =nums.size();
        int count =0;

        for(int i=0;i<n-2;i++){
            for(int j=i+1;j<n-1;j++){
                int sum = nums[i]+nums[j];
                for(int k=j+1;k<n;k++){
                    if(sum >nums[k]){
                        count ++;
                       
                    }
                }
            }
        }

        return count;
        
    }
}; 
```

But as n &lt;= 1000 it will give Time Limit error

### Optimal Approach using sorting -

Time Complexity - O(N^2)

Spacce Complexity - O(1)

```cpp
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // O(N^2)
        sort(nums.begin(),nums.end());
        int n =nums.size();
        int count =0;

        for(int i=n-1;i>=2;i--){
            int left =0,right =i-1;

            while(left <right){
                if(nums[left] + nums[right] <= nums[i]){
              // triangle only forms when sum of two sides 
            //is strictly greater than third side
                    left ++;
                }

                else {
           // since array is sorted it means we have to 
        //  take all element pair from left till right index
                    count += (right-left);
                    right--;
                }
            }
        }

        return count;
        
    }
};
```