611. Valid Triangle Number

1. Description

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.

2. Example

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

3. Note

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

4. Solutions

My Accepted Solution

n = m_nums.size()
Time complexity: O($n^2log_2n$)
Space complexity: O(1)

class Solution {
public:
    // int triangleNumber(vector<int>& nums)
    int triangleNumber(vector<int>& m_nums) {
        // the condition of edges to form a triangle is the sum of any two edges is greater than
        // the third edge, and the difference of any edges is less than the third edge, to
        // simplify the condition, we sort all edges. therefore, if a,b,c(the index of a is less
        // than the index of b, the index of b is less than the index of c) match the condition
        // a + b > c, then these three edges must could form a triangle
        sort(m_nums.begin(), m_nums.end());

        int count = 0;
        for (int i = 0; i + 2 < m_nums.size();
             ++i) {  // use i + 2 < m_nums.size() rather than
                     // i < m_nums.size() - 2, if the m_nums.size() is less than 2, it will overflow
            while (i < m_nums.size() && m_nums[i] <= 0) {
                i++;  // all edges should have a positive length
            }

            for (int j = i + 1; j + 1 < m_nums.size(); ++j) {
                auto iter =
                        lower_bound(m_nums.begin() + j + 1, m_nums.end(), m_nums[i] + m_nums[j]);
                int k = iter - m_nums.begin();

                count += k - j - 1;
            }
        }

        return count;
    }
};

4.1 Two Pointers

n = m_nums.size()
Time complexity: O($n^2$)
Space complexity: O(1)

class Solution {
public:
    // int triangleNumber(vector<int>& nums)
    int triangleNumber(vector<int>& m_nums) {
        // the condition of edges to form a triangle is the sum of any two edges is greater than
        // the third edge, and the difference of any edges is less than the third edge, to
        // simplify the condition, we sort all edges. therefore, if a,b,c(the index of a is less
        // than the index of b, the index of b is less than the index of c) match the condition
        // a + b > c, then these three edges must could form a triangle
        sort(m_nums.begin(), m_nums.end());

        int count = 0;
        for (int i = 0; i + 2 < m_nums.size();
             ++i) {  // use i + 2 < m_nums.size() rather than i <
                     // m_nums.size() - 2, if the m_nums.size() is less than 2, it will overflow
            while (i < m_nums.size() && m_nums[i] <= 0) {
                i++;  // all edges should have a positive length
            }

            int k = i + 2;
            for (int j = i + 1; j + 1 < m_nums.size(); ++j) {
                while (k < m_nums.size() && m_nums[i] + m_nums[j] > m_nums[k]) {
                    // even we have two loops here, while these two loops' time complexity is O(n). that's because k will not return to the j + 1, it just continue to increase. within the j's loop, it will increase, now that our array is sorted, its value must increase as well, so there is no need for k to go back to j + 1, it just need to increase to find a bigger valid number to form a triangle
                    ++k;
                }

                count += k - j - 1;
            }
        }

        return count;
    }
};

Algorithm Solutions

Search

Tags