Largest Perimeter Triangle

Problem

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

Constraints

• 3 <= nums.length <= 104
• 1 <= nums[i] <= 106

Solution

The problem Largest Perimeter Triangle can be solved using a greedy algorithm. After sorting the given array in a descending order, largest possible triangle can be formed from the first 3 lengths. If the first integer is equal to or larger than the sum of next 2 integers, then no other integers in the array can be used to form a triangle with the first integer because all other integers are equal to or smaller than the first 3 integers. Therefore, if the first 3 integers can form a triangle, it forms the largest triangle. If not, then the consecutive 3 pairs of integers can be checked until a valid triangle can be formed in which case it becomes the largest triangle that can be formed.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    int largestPerimeter(vector<int> &nums)
    {
        sort(nums.begin(), nums.end(), greater<int>());
        for (int i = 0; i < nums.size() - 2; i++)
            if (nums[i] < nums[i + 1] + nums[i + 2])
                return nums[i] + nums[i + 1] + nums[i + 2];

        return 0;
    }
};