LeetCode 611: Valid Triangle Number

Problem Description

LeetCode Problem 611

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

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

Difficulty: Medium

Tags: array, two pointers, binary search, greedy, sorting

Rating: 94.65%

Solution Approach

The key insight that leads to an efficient solution is that if we sort the array, we can simplify our triangle validation. Here’s why:

1. After sorting, if we choose three numbers a ≤ b ≤ c:
   • We only need to check if a + b > c
   • The other two conditions (b + c > a and a + c > b) are automatically satisfied because c is the largest
2. We can use the two-pointer technique to efficiently find valid pairs for each potential longest side.

Solution

Here’s my Python solution to this problem:

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)

        res = 0
        for i in range(n-1, 1, -1):
            l, r = 0, i-1

            while l < r:
                if nums[l] + nums[r] > nums[i]:
                    res += r - l
                    r -= 1 # Try to find more pairs with a smaller second number
                else:
                    l += 1 # Sum too small, need larger first number
    
        return res

How the Algorithm Works

Let’s walk through an example with nums = [2,2,3,4]:

1. First, we sort the array (already sorted in this case)
2. We start with i = 3 (nums[i] = 4):
   • Check if nums[0] + nums[2] > 4 (2 + 3 > 4): true
   • Add 2 combinations (using both 2’s with 3)
   • Move r pointer left
3. Next with i = 2 (nums[i] = 3):
   • Check if nums[0] + nums[1] > 3 (2 + 2 > 3): true
   • Add 1 combination
   • Move r pointer left

Complexity Analysis

The solution has the following complexity characteristics:

• Time Complexity: $O(n²)$
• Space Complexity: $O(1)$

Note: This is an automated analysis and may not capture all edge cases or specific algorithmic optimizations.