976. Largest Perimeter Triangle

Time: O(n log n)

Space: O(1)

Problem Overview

For three sides to form a triangle, the sum of the two smaller sides must exceed the largest side (triangle inequality).

Intuition

For three sides to form a triangle, the sum of the two smaller sides must exceed the largest side (triangle inequality). Sort descending so the first triple checked has the largest possible perimeter. The first valid consecutive triple after sorting is optimal.

Algorithm

1Sort array in descending order.
2For i from 0 to n-3: let a = A[i], b = A[i+1], c = A[i+2].
3If a < b + c, return a + b + c (largest sides first maximizes sum).
4If inequality fails, skip — a is too large relative to b and c; try next i.
5Return 0 if no triple satisfies the inequality.

Example Walkthrough

Input: nums = [2,1,2]

1.Sorted desc: [2,2,1]. Check 2 < 2+1 -> true.

Output: 5

Common Pitfalls

•Only check consecutive triples after sorting — non-consecutive triples cannot beat the greedy choice.
•Use long for sum if values are large (not needed for typical constraints).
•Strict inequality: equality (a == b+c) is NOT a valid triangle.

976.cs

// Approach: Sort descending; the first consecutive triple satisfying the triangle inequality gives the maximum perimeter.
// Time: O(n log n) Space: O(1)

public class Solution
{
    public int LargestPerimeter(int[] nums)
    {
        // Sort the array in ascending order to easily check triangle validity
        Array.Sort(nums);

        // Iterate from the largest elements to find the maximum perimeter
        // Start from the end and check consecutive triplets
        for (int i = nums.Length - 1; i >= 2; i--)
        {
            // Get the sum of the two smaller sides
            int sumOfTwoSmallerSides = nums[i - 1] + nums[i - 2];

            // Check triangle inequality: sum of two smaller sides must be greater than the largest side
            // If valid triangle is found, return its perimeter
            if (sumOfTwoSmallerSides > nums[i])
                return sumOfTwoSmallerSides + nums[i];
        }

        // No valid triangle found, return 0
        return 0;
    }
}

Was this solution helpful?