Largest Perimeter Triangle

Problem Statement

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.

Example: nums = [2,1,2] → Output: 5 (triangle with sides 2,1,2)
nums = [1,2,1] → Output: 0 (no valid triangle)

Approach 1: Sorting and Greedy Check

Explanation: Sort the array in descending order and check each triplet to see if it forms a valid triangle (sum of two sides > third side). Return the first valid perimeter.

Time Complexity: O(n log n)

Space Complexity: O(1)

sort(nums in descending order)
for i in range(0, n-2):
    a = nums[i]
    b = nums[i+1]
    c = nums[i+2]
    if b + c > a:
        return a + b + c
return 0

Approach 2: Brute Force

Explanation: Check all possible triplets in the array to find the largest valid triangle perimeter.

Time Complexity: O(n^3)

Space Complexity: O(1)

maxPerimeter = 0
for i in range(0, n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            a = nums[i]
            b = nums[j]
            c = nums[k]
            if a + b > c and b + c > a and a + c > b:
                maxPerimeter = max(maxPerimeter, a + b + c)
return maxPerimeter