Problem Link-
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.
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 <= 1000 it will give Time Limit error
Optimal Approach using sorting -
Time Complexity - O(N^2)
Spacce Complexity - O(1)
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;
}
};