Valid Triangle Number Solution in Python

Explore More Solutions

Problem Description

So, you think you can just throw three sticks together and hope they form a triangle? Well, think again! The Valid Triangle Number problem on LeetCode is here to remind you that not all combinations of lengths can create a triangle. In fact, for three lengths to form a triangle, the sum of any two lengths must be greater than the third.

Imagine you’re at a party, and you want to form a triangle with your friends. If one friend is too short (or too long), you might end up with a weird shape that nobody wants to be a part of. So, let’s figure out how many valid triangles we can form from a given list of stick lengths!

Code Solution


class Solution:
    def triangleNumber(self, nums: list[int]) -> int:
        ans = 0

        nums.sort()

        for k in range(len(nums) - 1, 1, -1):
            i = 0
            j = k - 1
            while i < j:
                if nums[i] + nums[j] > nums[k]:
                    ans += j - i
                    j -= 1
                else:
                    i += 1

        return ans

Approach Explanation

The approach taken in this code is quite clever. First, we sort the list of stick lengths. Then, we use a two-pointer technique to check for valid triangles. For each stick length (considered as the longest side), we look for pairs of other lengths that can form a triangle with it. If the sum of the two shorter lengths is greater than the longest length, we have a valid triangle! We count all such pairs and keep track of the total.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n^2)
Space Complexity	O(1)

Real-World Example

Let’s say you’re trying to build a tent with three poles. If one pole is too short, and the other two are too long, you might end up with a tent that looks more like a pancake than a shelter. The Valid Triangle Number problem helps you determine how many combinations of poles can actually stand up and form a proper tent!