Problem Statement

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

Example 1:

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Example 2:

Input: nums = [4,2,3,4]
Output: 4

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

Problem Link

Valid Triangle Number - LeetCode

Code

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        
        int n = nums.size();
        
        sort(nums.begin(),nums.end(),greater<int>());
        
        int res = 0;
        
        for(int i=0;i<n;i++)
        {
            int left = i+1;
            int right = n-1;
            
            while(left<right)
            {
                if(nums[left]+nums[right]>nums[i])
                {
                    res+=(right-left);
                    left++;
                }
                else
                    right--;
            }
        }
        
        return res;
        
    }
};