From 23353c144ac9b158af7616dc46b636d53b73ce34 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Thu, 25 Sep 2025 21:03:37 -0600 Subject: 611. valid triangle number --- valid_triangle_number.py | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) create mode 100644 valid_triangle_number.py (limited to 'valid_triangle_number.py') diff --git a/valid_triangle_number.py b/valid_triangle_number.py new file mode 100644 index 0000000..8460292 --- /dev/null +++ b/valid_triangle_number.py @@ -0,0 +1,31 @@ +# 611. Valid Triangle Number + +""" +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 +""" + + +class Solution(object): + def triangleNumber(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + nums.sort() + n, ans = len(nums), 0 + for k in range(2, n): + i, j = 0, k - 1 + while i < j: + if nums[i] + nums[j] > nums[k]: + ans += j - i + j -= 1 + else: + i += 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.triangleNumber(nums=[2, 2, 3, 4])) + print(obj.triangleNumber(nums=[4, 2, 3, 4])) -- cgit v1.2.3