611. Valid Triangle Number Medium

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.

Example 1:
Input: nums = [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

Example 2:
Input: nums = [4,2,3,4]
Output: 4

Approach

Input: A non-negative integer array nums

Output: Return the number of combinations that can form a triangle

This is a Sorting + Opposite-direction Two Pointers problem.

The three sides of a triangle must satisfy the condition: the sum of any two sides > the third side.

Assuming the sorted array is nums[0] <= nums[1] <= ... <= nums[n-1], then the triplet (i, j, k) we are looking for must satisfy:

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

We can sort the array, fix the longest side k, and then find combinations that meet the conditions using two pointers i and j from the front.

As long as the condition is met, it means all combinations between [i, j] satisfy the condition. We can directly add j - i to the count, and then move j -= 1 to decrease the side length and continue searching.

If the condition is not met, we need to move i += 1 to increase the side length.

Implementation

python

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        # First query the array to sort it, making it easier to use two pointers later
        nums.sort()
        n = len(nums)
        count = 0

        # Enumerate each valid longest side at index k, from back to front
        for k in range(n - 1, -1, -1):
            i, j = 0, k - 1  # i starts from the beginning, j starts from the position just before k

            # Two pointers determine whether the triangle condition is met: nums[i] + nums[j] > nums[k]
            while i < j:
                if nums[i] + nums[j] > nums[k]:
                    # If the condition is met, all i between i and j satisfy the condition, total j - i combinations
                    count += j - i
                    j -= 1  # Shrink the right boundary
                else:
                    i += 1  # Increase the left boundary to try a larger nums[i]
        
        # Return the number of all valid triplets
        return count

javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function(nums) {
    nums.sort((a, b) => a - b);
    let count = 0;

    for (let k = nums.length - 1; k > 0; k--) {
        let i = 0;
        let j = k - 1;

        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) {
                count += j - i;
                j--;
            } else {
                i++;
            }
        }
    }

    return count;
};

Complexity Analysis

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Links

611. Valid Triangle Number (English)611. 有效三角形的个数 (Chinese)