Valid Triangle Number - Array - Medium - LeetCode

1 min read 121 words

sumitc9121 November 2020Updated: 21 November 2020 1 min read

ShareWhatsApp Post on X

1The task is to count triplets in an array that can form valid triangles using their side lengths.
2The algorithm sorts the array and uses a two-pointer approach to efficiently count valid combinations.
3The solution has a time complexity of O(n^2) and a space complexity of O(1).

AI-generated summary · May not capture all nuances

Key Insight

AskGif

"The task is to count triplets in an array that can form valid triangles using their side lengths."

— Valid Triangle Number - Array - Medium - LeetCode

Given an array consists of non-negative integers, your task is to count 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: [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 Note: The length of the given array won't exceed 1000. The integers in the given array are in the range of [0, 1000].

public class Solution {
 public int TriangleNumber(int[] nums) {
 Array.Sort(nums);
 int count = 0;
 for(int i=nums.Length-1;i>=2;i--){
 int l=0;
 int r = i-1;
 while(l<r){
 if(nums[l]+nums[r]>nums[i]){
 count+= r-l;
 r--;
 }
 else{
 l++;
 } 
 }
 }
 
 return count;
 }
}

Time Complexity: O(n^2)

Space Complexity: O(1)

🛒 You'll Need This

Products related to this article