Medium

Valid Triangle Number

LAB

Return how many index triplets can form a triangle from side lengths in nums.

EXAMPLES

Example 1

Input
{
  "nums": [
    2,
    2,
    3,
    4
  ]
}

Output
3

FUNCTION SHAPE

nums: intArray→int

SOLUTION NOTE

We invoke the triangle inequality: in a triangle, any two sides have sum greater than the third, i.e., a + b > c for any 3 sides. This is strongest when c is the largest side.

Fix the largest side c at index k. Now count all pairs (i,j) s.t A[i] + A[j] > c, where i < j < k.

If nums[i] + nums[j] > nums[k], this is valid. Given (i,j), all pairs (m, j) for m: i <= m < j have sum > nums[k] because nums is sorted. So we increment res by j-i, then decrement j since we've counted all valid subarrays ending at j.

Reveal reference solution +

pythonREFERENCE

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

    for k in range(n):
        i = 0
        j = k - 1

        while i < j:
            if nums[i] + nums[j] > nums[k]:
                res += j - i
                j -= 1
            else:
                i += 1

    return res

TimeO(n²)

SpaceO(1)

Open on LeetCode ↗