aboutsummaryrefslogtreecommitdiff
path: root/valid_triangle_number.py
blob: 84602927d4a8c47ee246b53e990be0d81066c21a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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]))