976. Largest Perimeter Triangle

2020, Nov 08 One min read

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

Sorting

n = m_edges.size()
Time complexity: O($nlog_2n$)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// 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;
    }
};

Search

Tags