Specials

Question 1

Solve

Given an array of non-negative integers nums, return the number of triplets chosen from the array that can make a valid triangle. A triplet (nums[i], nums[j], nums[k]) forms a triangle if: a + b > c and a ≤ b ≤ c. In other words, nums[i] and nums[j] are each smaller than nums[k]

Input: nums
Output: count of triplets for a valid triangle

Answer 1

def triangleNumber(nums):
    nums.sort()
    count = 0
    n = len(nums)
    
    for k in range(n - 1, 1, -1):
        i, j = 0, k - 1
        while i < j:
            if nums[i] + nums[j] > nums[k]:
                count += j - i
                j -= 1
            else:
                i += 1
    return count