976. Largest Perimeter Triangle
1. Description
Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.
If it is impossible to form any triangle of non-zero area, return 0.
2. Example
Example 1:
Input: [2,1,2]
Output: 5
Example 2:
Input: [1,2,1]
Output: 0
Example 3:
Input: [3,2,3,4]
Output: 10
Example 4:
Input: [3,6,2,3]
Output: 8
3. Note
- 3 <= A.length <= 10000
- 1 <= A[i] <= $10^6$
4. Solutions
My Accepted Solution
n = m_edges.size()
Time complexity: O($nlog_2n$)
Space complexity: O(1)
// the conditon to form a triangle: the sum of any two edges is bigger than the third one
class Solution
{
public:
// int largestPerimeter(vector<int>& A)
int largestPerimeter(vector<int> &m_edges)
{
sort(m_edges.begin(), m_edges.end(), [](int left, int right){return left >= right;});
for(int i = 0; i + 2 < m_edges.size(); i++)
{
if(m_edges[i] < m_edges[i+1] + m_edges[i+2])
return m_edges[i] + m_edges[i+1] + m_edges[i+2];
}
return 0;
}
};