Skip to content

611. Valid Triangle Number

Array Two Pointers Binary Search Greedy Sorting

Problem - 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

 

Constraints:

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

Solutions

1
2
3
4
5
6
7
8
9
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        result, n = 0, len(nums)
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                k = bisect_left(nums, nums[i] + nums[j], lo=j+1) - 1
                result += k - j
        return result

Submission Stats:

  • Runtime: 1312 ms (11.71%)
  • Memory: 17.8 MB (82.72%)