Problem statement

Given an integer array nums, return the largest perimeter of a triangle with non-zero area whose three side lengths are taken from nums. If no such triangle exists, return 0.

Example 1

Input: nums = [2,1,2]
Output: 5

Example 2

Input: nums = [1,2,1,10]
Output: 0
Explanation: No three of these can form a triangle.

Example 3

Input: nums = [3,6,2,3]
Output: 8

Constraints

• 3 <= nums.length <= 40
• 1 <= nums[i] <= 1000

Hints for Largest Perimeter Triangle

1. Hint 1

   Three lengths form a triangle exactly when the largest is strictly less than the sum of the other two.

2. Hint 2

   Sort descending; the first consecutive triple that satisfies the inequality is the best possible.

3. Hint 3

   Skipping past a failing triple is safe — any other triple with that same largest side is even smaller.

How to solve Largest Perimeter Triangle

Sort descending; the first consecutive triple with a < b + c (largest side strictly less than the sum of the other two) has the largest perimeter.

Approach

1. Sort descending.
2. For each i, if a[i] < a[i+1] + a[i+2], return their sum.
3. Return 0.

Why it works

For a fixed largest side, the two next-largest sides give the best chance of satisfying the inequality and the largest perimeter; if they fail, no other pair with that largest side succeeds, so moving on is safe.

Complexity

• Time — O(n log n)
• Space — O(1) beyond the sort

Pitfalls

• The inequality is strict — degenerate triangles have zero area.

Reference solution

Python

def largestPerimeter(nums) -> int:
    ordered = sorted(nums, reverse=True)
    for i in range(len(ordered) - 2):
        if ordered[i] < ordered[i + 1] + ordered[i + 2]:
            return ordered[i] + ordered[i + 1] + ordered[i + 2]
    return 0

Java

public static int largestPerimeter(int[] nums) {
    int[] s = nums.clone();
    Arrays.sort(s);
    for (int i = s.length - 1; i >= 2; i--) {
        if (s[i] < s[i - 1] + s[i - 2]) return s[i] + s[i - 1] + s[i - 2];
    }
    return 0;
}

C++

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

JavaScript

var largestPerimeter = function(nums) {
    const sorted = nums.slice().sort(function(a, b) { return b - a; });
    for (let i = 0; i + 2 < sorted.length; i++) {
        if (sorted[i] < sorted[i + 1] + sorted[i + 2]) {
            return sorted[i] + sorted[i + 1] + sorted[i + 2];
        }
    }
    return 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy