Valid Triangle Number Python Solution

Tested Python solution for LeetCode 611 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 611, Medium. Topics: Array, Two Pointers, Binary Search, Greedy, Sorting. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 20 parametrized pytest cases, and a playground notebook:

lcpy gen -n 611   # by problem number
lcpy gen -s valid_triangle_number   # by problem name

​

Problem

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.

​

Examples

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

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

​

Constraints

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

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n^2)
    # Space: O(1) extra (sorting not counted)
    def triangle_number(self, nums: list[int]) -> int:
        nums = sorted(nums)
        count = 0
        for k in range(len(nums) - 1, 1, -1):
            left, right = 0, k - 1
            while left < right:
                if nums[left] + nums[right] > nums[k]:
                    count += right - left
                    right -= 1
                else:
                    left += 1
        return count

​

Complexity

Time	Space
O(n^2)	O(1) extra (sorting not counted)

​

Tags