Problem Statement

You are given an integer array nums, where each element represents the length of a side of a potential triangle. Your task is to return the largest perimeter of a triangle with a non-zero area that can be formed by picking three lengths from the array. If it is impossible to form any triangle with a non-zero area, return 0.

A triangle can have a non-zero area if and only if the sum of the lengths of any two sides is greater than the length of the third side. Mathematically, for three sides a, b, and c where a <= b <= c, the triangle inequality condition is:

a + b >= c

Examples

Example 1:

Input: nums = [1, 2, 3, 4, 5]
Output: true

Explanation: Any triplet where i < j < k is valid.

Example 2:

Input: nums = [5, 4, 3, 2, 1]
Output: false

Explanation: No triplet exists.

Example 3:

Input: nums = [2, 1, 5, 0, 4, 6]
Output: true

Explanation:The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

Different Approaches

1️⃣ Sorting:

Intuition:

To form a triangle with three sides, the triangle inequality theorem must hold: the sum of the lengths of any two sides must be greater than the third side.

Given this condition, we can try to find the largest perimeter by:

1. Sorting the array in non-decreasing order.
2. Checking triplets of consecutive elements starting from the largest to the smallest (because larger numbers will yield larger perimeters).
3. For a valid triangle, return the perimeter of the first valid triplet found.

Steps:

1. Sort the array: Sorting makes it easier to find valid triangles because we only need to check if the sum of the two smallest numbers is greater than the largest number.
2. Iterate from the end: After sorting, we try to form a triangle using the three largest values. If they form a valid triangle (i.e., the sum of the two smaller values is greater than the largest), we return the perimeter.
3. Return 0 if no valid triangle is found.

Approach:

1. Sort the array in non-decreasing order.
2. Start from the largest elements (from the end) and check triplets:
   • If the triplet satisfies the triangle condition (nums[i] + nums[i-1] > nums[i-2]), return their perimeter.
3. If no valid triplet is found, return 0.

Code:

#include <vector>
#include <algorithm>

int largestPerimeter(std::vector<int>& nums) {
    // Step 1: Sort the array in non-decreasing order
    std::sort(nums.begin(), nums.end());

    // Step 2: Check triplets from the largest elements
    for (int i = nums.size() - 1; i >= 2; --i) {
        // Check if the triplet (nums[i-2], nums[i-1], nums[i]) forms a valid triangle
        if (nums[i] < nums[i-1] + nums[i-2]) {
            // If valid, return the perimeter of the triangle
            return nums[i] + nums[i-1] + nums[i-2];
        }
    }

    // Step 3: If no valid triangle found, return 0
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n logn)
  • Sorting the array takes O(n log n), where n is the number of elements in the input array.
  • After sorting, checking each triplet takes O(n).
  • So the overall time complexity is O(n log n)
• Space Complexity: O(1)
  • Because the sorting is done in-place, and we only use a few exra variables.