O(N^2) solution for C++ & Python


  • 1
    Z

    c++

    class Solution {
    public:
        int triangleNumber(vector<int>& nums) {
            vector<int> snums(nums);
            sort(snums.begin(), snums.end());
            int count = 0;
            for ( int n = nums.size(), k = n - 1; k > 1; --k ) {
                int i = 0, j = k - 1;
                while ( i < j ) {
                    // any value x between i...j will satisfy snums[x] + snums[j] > snums[k]
                    // and because snums[k] > snums[j] > snums[x] >= 0, they will always satisfy
                    // snums[k] + snums[x] > snums[j] and snums[k] + snums[j] > snums[x]
                    if ( snums[i] + snums[j] > snums[k] )
                        count += --j - i + 1;
                    else
                        ++i;
                }
            }
            return count;
        }
    };
    
    // 243 / 243 test cases passed.
    // Status: Accepted
    // Runtime: 59 ms
    

    python solution, sometimes it might fail TLE

    class Solution(object):
        def triangleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            nums, count, n = sorted(nums, reverse=1), 0, len(nums)
            for i in xrange(n):
                j, k = i + 1, n - 1
                while j < k:
                    # any value x between j...k will satisfy nums[j] + nums[x] > nums[i]
                    # and because nums[i] > nums[j] > nums[x] >= 0, they will always satisfy
                    # nums[i] + nums[x] > nums[j] and nums[i] + nums[j] > nums[x]
                    if nums[j] + nums[k] > nums[i]:
                        count += k - j
                        j += 1
                    else:
                        k -= 1
            return count
    
    # 243 / 243 test cases passed.
    # Status: Accepted
    # Runtime: 1855 ms
    

  • 0
    C

    Great solution. This took advantage of the range of values that will satisfy the triangle inequality. This should get more up votes.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.