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
💡 Think: Sort descending and scan triplets; the first that satisfies b + c > a gives the maximum perimeter.
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
💡 Think: Try every triplet and keep the best perimeter that satisfies triangle inequality.