We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Valid Triangle Number

Difficulty: Medium

Problem Description

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.

Key Insights

  • A triangle can be formed by three sides a, b, and c if and only if the sum of the lengths of any two sides is greater than the length of the third side (Triangle Inequality Theorem).
  • When sorted, for any triplet (a, b, c), if a + b > c, then the other two conditions (a + c > b and b + c > a) will automatically hold true.
  • Sorting the array allows us to efficiently find valid triplets using a two-pointer technique.

Space and Time Complexity

Time Complexity: O(n^2) - where n is the length of the input array (due to the nested loops). Space Complexity: O(1) - no significant additional space is used.

Solution

To solve the problem, we first sort the input array. Then, for each pair of elements (nums[i], nums[j]), we can use a two-pointer approach to find the third element (nums[k]) that can form a triangle with these two. We count all valid triplets by ensuring that nums[i] + nums[j] > nums[k]. This approach leverages sorting and the properties of triangles to efficiently count valid combinations.

Code Solutions

def triangleNumber(nums):
    nums.sort()  # Sort the array
    count = 0
    n = len(nums)

    for i in range(n - 2):  # Fix the first side
        k = i + 2  # Initialize the third side
        for j in range(i + 1, n - 1):  # Fix the second side
            while k < n and nums[i] + nums[j] > nums[k]:  # Check the triangle condition
                k += 1
            count += k - j - 1  # Count valid triangles

    return count
← Back to All Questions