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