Leetcode: Valid Triangle Number

Pic 3 numbers to get a triangle



Similar Problems:


Given an array consists of non-negative integers, your task is to count 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: [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

Note:

  1. The length of the given array won’t exceed 1000.
  2. The integers in the given array are in the range of [0, 1000].

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/valid-triangle-number
## Basic Ideas: Like 3sum
##       Sort the list, then use 3 loop
##       When the sum 2 shorter sides is greater 
##       than the big side, the 3 numbers can form a triangle.
##       Note: not O(n*n*n); numbers has 0; allow duplicate
##
## Complexity: Time O(n^2), Space O(1)
## Sample Data:
##     3, 5, 6, 7, 7, 8
##     i  j        k
##     2  2  3  4
##     0  0  1  1
class Solution(object):
    def triangleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        res = 0
        for i in range(0, len(nums)-2):
            if nums[i] == 0:
                continue
            count = 0
            k = i + 2
            for j in range(i+1, len(nums)-1):
                # k never need to move back

                # calculate current round of matches based on last round
                if (j>i+1) and (nums[i]+nums[j]>nums[k-1]):
                    count -= 1

                while k<len(nums) and nums[i]+nums[j]>nums[k]:
                    count += 1
                    k += 1
                res += count
        return res
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.