LeetCode 611: Valid Triangle Number

Problem Restatement

We are given an integer array nums.

Each value can be treated as a side length.

We need to count how many triplets can form a valid triangle. A triplet means choosing three different indices from the array.

The official problem asks us to return the number of triplets chosen from nums that can make triangles if we take them as side lengths. The constraints are 1 <= nums.length <= 1000 and 0 <= nums[i] <= 1000.

Input and Output

Function signature:

def triangleNumber(nums: list[int]) -> int:
    ...

Input:

Output:

Examples

Example 1:

nums = [2, 2, 3, 4]

Valid triplets are:

Output:

3

Example 2:

nums = [4, 2, 3, 4]

After sorting:

[2, 3, 4, 4]

Valid triplets are:

Output:

4

First Thought: Check Every Triplet

The direct solution is to try every possible group of three indices.

For each triplet, check the triangle inequality:

a + b > c
a + c > b
b + c > a

This works, but it uses three nested loops.

For an array of length n, the time complexity is:

O(n^3)

Since n can be up to 1000, this is too slow.

Key Insight

Sort the array first.

After sorting, suppose we choose three sides:

a <= b <= c

Then we only need to check one condition:

a + b > c

The other two are automatically true because c is the largest side.

So the problem becomes:

For each largest side c, count how many pairs (a, b) before it satisfy:

a + b > c

This is a two-pointer problem.

Algorithm

Sort nums.

Then fix the largest side by index k, moving from right to left.

For each k:

1. Set left = 0.
2. Set right = k - 1.
3. While left < right:
   • If nums[left] + nums[right] > nums[k], then every value from left through right - 1 can pair with nums[right].
   • Add right - left to the answer.
   • Move right leftward.
   • Otherwise, the sum is too small, so move left rightward.

Why can we add right - left?

Because the array is sorted.

If:

nums[left] + nums[right] > nums[k]

then for every index i where:

left <= i < right

we also have:

nums[i] + nums[right] >= nums[left] + nums[right] > nums[k]

So all those pairs are valid.

Implementation

class Solution:
    def triangleNumber(self, nums: list[int]) -> int:
        nums.sort()

        count = 0
        n = len(nums)

        for k in range(n - 1, 1, -1):
            left = 0
            right = k - 1

            while left < right:
                if nums[left] + nums[right] > nums[k]:
                    count += right - left
                    right -= 1
                else:
                    left += 1

        return count

Code Explanation

First, sort the array:

nums.sort()

Sorting lets us treat nums[k] as the largest side when k is fixed.

The outer loop chooses the largest side:

for k in range(n - 1, 1, -1):

For each largest side, we search for valid pairs in the prefix:

left = 0
right = k - 1

Now compare the smallest available side with the current right side:

if nums[left] + nums[right] > nums[k]:

If this is true, then all pairs:

(left, right), (left + 1, right), ..., (right - 1, right)

are valid.

So we add:

count += right - left

Then we move right leftward:

right -= 1

If the sum is too small, we need a larger left side:

else:
    left += 1

At the end, count contains the number of valid triplets.

Correctness

After sorting, every triplet chosen with indices i < j < k has side lengths:

nums[i] <= nums[j] <= nums[k]

So the triplet forms a valid triangle exactly when:

nums[i] + nums[j] > nums[k]

The algorithm fixes k as the largest side and uses two pointers to count all pairs (i, j) with i < j < k satisfying that condition.

When nums[left] + nums[right] > nums[k], every index from left to right - 1 also forms a valid pair with right, because those values are at least nums[left]. The algorithm counts exactly those right - left pairs.

When nums[left] + nums[right] <= nums[k], the current left value is too small to pair with right. Since any smaller or equal left-side candidate would also fail, the algorithm safely moves left rightward.

Thus, for each fixed k, all valid pairs are counted exactly once. Since every valid triplet has exactly one largest index k, the final answer is exactly the number of valid triangle triplets.

Complexity

Let n be the length of nums.

In Python, sort() may use additional internal memory, but the algorithm itself uses constant extra space.

Alternative: Sorting and Binary Search

For each pair (i, j), we can binary search for the largest k such that:

nums[i] + nums[j] > nums[k]

from bisect import bisect_left

class Solution:
    def triangleNumber(self, nums: list[int]) -> int:
        nums.sort()

        count = 0
        n = len(nums)

        for i in range(n - 2):
            if nums[i] == 0:
                continue

            for j in range(i + 1, n - 1):
                limit = nums[i] + nums[j]
                k = bisect_left(nums, limit, j + 1, n)
                count += k - j - 1

        return count

This version is also correct, but it runs in:

O(n^2 log n)

The two-pointer solution is faster.

Testing

def run_tests():
    s = Solution()

    assert s.triangleNumber([2, 2, 3, 4]) == 3
    assert s.triangleNumber([4, 2, 3, 4]) == 4
    assert s.triangleNumber([1, 1, 1, 1]) == 4
    assert s.triangleNumber([0, 0, 0]) == 0
    assert s.triangleNumber([1, 2, 3]) == 0
    assert s.triangleNumber([2, 3, 4, 5, 6]) == 7

    print("all tests passed")

run_tests()

Test coverage: