LeetCode 976: Largest Perimeter Triangle

Problem Restatement

We are given an integer array nums.

Each number represents a possible side length of a triangle.

We need to choose three lengths that can form a triangle with non-zero area. Among all valid choices, return the largest possible perimeter.

If no three lengths can form a valid triangle, return 0.

A valid triangle with side lengths a, b, and c must satisfy the triangle inequality. If the sides are sorted so that:

a <= b <= c

then we only need to check:

a + b > c

The official constraints are 3 <= nums.length <= 10^4 and 1 <= nums[i] <= 10^6.

Input and Output

Function shape:

def largestPerimeter(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [2, 1, 2]

After sorting:

[1, 2, 2]

Check the three sides:

1 + 2 > 2

This is true, so these sides form a valid triangle.

The perimeter is:

1 + 2 + 2 = 5

Answer:

5

Example 2:

nums = [1, 2, 1, 10]

After sorting:

[1, 1, 2, 10]

Check the largest three values:

1 + 2 > 10

False.

Check the next three values:

1 + 1 > 2

False.

No valid triangle exists.

Answer:

0

First Thought: Brute Force

The direct solution is to try every group of three numbers.

For every triple (i, j, k), compute the side lengths and check whether they form a valid triangle.

If they do, compute the perimeter and keep the maximum.

class Solution:
    def largestPerimeter(self, nums: list[int]) -> int:
        n = len(nums)
        best = 0

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    sides = sorted([nums[i], nums[j], nums[k]])
                    a, b, c = sides

                    if a + b > c:
                        best = max(best, a + b + c)

        return best

This checks all possible triples, so it is correct.

Problem With Brute Force

The brute force solution checks O(n^3) triples.

Since nums.length can be as large as 10^4, this is too slow.

We need to avoid enumerating every combination.

Key Insight

To maximize the perimeter, we want large side lengths.

So we sort the array.

Then we inspect triples from largest to smallest.

After sorting:

nums.sort()

For any three sides:

a <= b <= c

the only condition we need to check is:

a + b > c

The other two inequalities are automatically true because c is already the largest side.

Now consider a sorted array.

For a fixed largest side nums[i], the best possible two smaller sides are:

nums[i - 2], nums[i - 1]

They are the two largest values before nums[i].

If these two cannot form a triangle with nums[i], then no smaller pair can form a triangle with nums[i].

So we only need to check consecutive triples from right to left.

Algorithm

Sort nums in ascending order.

Start from the last index and check each triple:

nums[i - 2], nums[i - 1], nums[i]

For each triple:

1. Let a = nums[i - 2].
2. Let b = nums[i - 1].
3. Let c = nums[i].
4. If a + b > c, return a + b + c.
5. Otherwise, move left and try the next triple.

If no valid triple is found, return 0.

Correctness

After sorting, every checked triple has the form:

a <= b <= c

For such a triple, the triangle has non-zero area exactly when:

a + b > c

The algorithm checks triples from the largest possible side lengths down to smaller ones.

When it checks index i, the values nums[i - 2] and nums[i - 1] are the two largest available values smaller than or equal to nums[i].

If:

nums[i - 2] + nums[i - 1] <= nums[i]

then any other pair before i has a sum less than or equal to that sum, so no pair with nums[i] can form a valid triangle.

If:

nums[i - 2] + nums[i - 1] > nums[i]

then the triple is valid.

Because we scan from the largest values downward, the first valid triple has the largest possible perimeter. Returning it is correct.

If the scan finishes without finding a valid triple, then no valid triangle can be formed, so returning 0 is correct.

Complexity

Implementation

class Solution:
    def largestPerimeter(self, nums: list[int]) -> int:
        nums.sort()

        for i in range(len(nums) - 1, 1, -1):
            a = nums[i - 2]
            b = nums[i - 1]
            c = nums[i]

            if a + b > c:
                return a + b + c

        return 0

Code Explanation

We first sort the side lengths:

nums.sort()

This lets us reason about each triple as:

a <= b <= c

Then we scan from the end:

for i in range(len(nums) - 1, 1, -1):

At each position, nums[i] is the largest side in the current triple.

The two sides before it are the largest possible companions:

a = nums[i - 2]
b = nums[i - 1]
c = nums[i]

We check the triangle inequality:

if a + b > c:

If true, we return the perimeter:

return a + b + c

If no triple passes the check, no valid triangle exists:

return 0

Testing

def run_tests():
    s = Solution()

    assert s.largestPerimeter([2, 1, 2]) == 5
    assert s.largestPerimeter([1, 2, 1, 10]) == 0
    assert s.largestPerimeter([3, 2, 3, 4]) == 10
    assert s.largestPerimeter([3, 6, 2, 3]) == 8
    assert s.largestPerimeter([1, 1, 2]) == 0
    assert s.largestPerimeter([5, 5, 5]) == 15

    print("all tests passed")

run_tests()