LeetCode 976 - Largest Perimeter Triangle

LeetCode Problem 976

Difficulty: 🟢 Easy
Topics: Array, Math, Greedy, Sorting

Solution

Problem Understanding

The problem gives us an array of integers called nums, where each integer represents a possible side length. Our goal is to select exactly three lengths that can form a valid triangle with a non-zero area, and among all valid triangles, return the maximum possible perimeter.

A triangle is only valid if the sum of the two smaller sides is strictly greater than the largest side. This is known as the triangle inequality theorem. If this condition is not satisfied, the three lengths either form a degenerate triangle with zero area or cannot form a triangle at all.

For example, the side lengths [1, 2, 2] form a valid triangle because:

$1 + 2 > 2$

The perimeter is:

$1 + 2 + 2 = 5$

On the other hand, [1, 1, 2] is invalid because:

$1 + 1 = 2$

This creates a degenerate triangle with zero area, which the problem explicitly disallows.

The input constraints are important:

• The array length can be as large as 10^4
• Each value can be as large as 10^6

These constraints tell us that an extremely slow cubic solution may not be efficient enough. We need something substantially better than checking every possible triplet in practice.

Several edge cases are important:

• Arrays where no triangle can be formed at all
• Arrays where multiple valid triangles exist, but only one has the largest perimeter
• Arrays with repeated values
• Arrays already sorted or completely unsorted
• Very small arrays of exactly three elements

The problem guarantees that the array has at least three numbers, so we never need to handle arrays with fewer than three elements.

Approaches

Brute Force Approach

The most direct solution is to examine every possible combination of three numbers from the array. For each triplet, we check whether it satisfies the triangle inequality theorem. If it does, we compute its perimeter and track the maximum.

This approach is correct because it exhaustively evaluates all possible triangles, so it cannot miss the optimal answer.

However, the runtime is too expensive. If the array contains n elements, there are:

$\binom{n}{3} = \frac{n(n-1)(n-2)}{6}$

possible triplets.

With n = 10^4, this becomes computationally infeasible. A cubic-time algorithm would perform billions of operations.

Optimal Greedy Approach

The key observation comes from sorting the array.

Suppose the array is sorted in non-decreasing order. For any three consecutive elements:

a <= b <= c

The only condition we need to check is:

$a + b > c$

The other two triangle inequalities are automatically true because all side lengths are positive.

Now consider perimeter maximization. Since we want the largest perimeter, we should try the largest values first. After sorting, we can scan from the end of the array toward the beginning.

The moment we find three numbers that satisfy the triangle inequality, we can immediately return their sum. This works because:

• We are checking the largest side lengths first
• Any later triplet will have equal or smaller values
• Therefore, the first valid triangle encountered must have the maximum perimeter

This transforms the problem into a sorting problem followed by a linear scan.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every possible triplet
Optimal	O(n log n)	O(1) or O(log n) depending on sorting implementation	Sorts array and greedily checks largest triplets

Algorithm Walkthrough

1. Sort the array in non-decreasing order.

Sorting is essential because it allows us to reason about side relationships efficiently. Once sorted, the largest side in any candidate triplet is always the rightmost element. 2. Start iterating from the end of the array.

Since we want the maximum perimeter, we examine the largest numbers first. 3. For each index i, consider the triplet:

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

These are three consecutive elements in sorted order. 4. Check the triangle inequality condition.

Since the array is sorted:

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

We only need to verify:

$nums[i-2] + nums[i-1] > nums[i]$ 5. If the condition is true, return the perimeter immediately.

The perimeter is:

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

Because we are scanning from largest to smallest values, this is guaranteed to be the largest possible perimeter. 6. If no valid triplet is found, return 0.

This means no three numbers in the array can form a valid triangle.

Why it works

The correctness relies on two properties:

• In a sorted array, the triangle inequality only needs to be checked once for each triplet.
• By scanning from the largest elements downward, the first valid triangle encountered automatically has the maximum possible perimeter.

Any later candidate would contain smaller side lengths and therefore cannot produce a larger perimeter.

Python Solution

from typing import List

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

        for i in range(len(nums) - 1, 2, -1):
            if nums[i - 2] + nums[i - 1] > nums[i]:
                return nums[i - 2] + nums[i - 1] + nums[i]

        return 0

The implementation begins by sorting the array in ascending order. This enables efficient triangle validation and guarantees that larger perimeters are considered first.

The loop starts from the final index and moves backward. At each step, the code examines three consecutive elements:

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

Because the array is sorted, nums[i] is the largest side. The code checks whether the sum of the two smaller sides exceeds the largest side.

If the condition is satisfied, the function immediately returns the perimeter because this is the largest valid triangle possible.

If the loop completes without finding a valid triangle, the function returns 0.

Go Solution

package main

import "sort"

func largestPerimeter(nums []int) int {
	sort.Ints(nums)

	for i := len(nums) - 1; i >= 2; i-- {
		if nums[i-2]+nums[i-1] > nums[i] {
			return nums[i-2] + nums[i-1] + nums[i]
		}
	}

	return 0
}

The Go implementation follows the exact same logic as the Python version. The primary difference is the use of sort.Ints(nums) from Go's standard library to sort the slice in place.

Go slices are mutable references to arrays, so sorting modifies the original slice directly. Integer overflow is not a concern here because the maximum possible perimeter is:

3 * 10^6

which easily fits inside Go's int type on modern platforms.

Worked Examples

Example 1

Input: nums = [2,1,2]

After sorting:

[1,2,2]

We start from the end.

i	Triplet	Check	Valid?	Perimeter
2	(1,2,2)	1 + 2 > 2	Yes	5

Since the first checked triplet is valid, we immediately return 5.

Example 2

Input: nums = [1,2,1,10]

After sorting:

[1,1,2,10]

We scan from right to left.

i	Triplet	Check	Valid?
3	(1,2,10)	1 + 2 > 10	No
2	(1,1,2)	1 + 1 > 2	No

No valid triangle exists, so the algorithm returns 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(log n)	Depends on sorting implementation details

The linear scan after sorting takes only O(n) time. The dominant operation is sorting, which requires O(n log n) time.

The algorithm itself does not allocate extra data structures. However, internal sorting implementations may use recursion or auxiliary memory, so the practical space complexity depends on the language runtime.

Test Cases

from typing import List

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

        for i in range(len(nums) - 1, 2, -1):
            if nums[i - 2] + nums[i - 1] > nums[i]:
                return nums[i - 2] + nums[i - 1] + nums[i]

        return 0

solution = Solution()

assert solution.largestPerimeter([2, 1, 2]) == 5  # basic valid triangle
assert solution.largestPerimeter([1, 2, 1, 10]) == 0  # no valid triangle
assert solution.largestPerimeter([3, 2, 3, 4]) == 10  # multiple valid choices
assert solution.largestPerimeter([3, 6, 2, 3]) == 8  # must skip invalid largest side
assert solution.largestPerimeter([1, 1, 1]) == 3  # smallest valid triangle
assert solution.largestPerimeter([1, 1, 2]) == 0  # degenerate triangle
assert solution.largestPerimeter([5, 5, 5, 5]) == 15  # repeated values
assert solution.largestPerimeter([1000000, 1000000, 1000000]) == 3000000  # large values
assert solution.largestPerimeter([1, 2, 3, 4, 5, 6]) == 15  # larger sorted input
assert solution.largestPerimeter([6, 5, 4, 3, 2, 1]) == 15  # reverse sorted input

Test Case Summary

Test	Why
[2,1,2]	Basic valid triangle
[1,2,1,10]	No possible triangle
[3,2,3,4]	Multiple valid combinations
[3,6,2,3]	Largest side may need to be skipped
[1,1,1]	Minimum valid equal-sided triangle
[1,1,2]	Degenerate triangle case
[5,5,5,5]	Duplicate values
[1000000,1000000,1000000]	Large constraint values
[1,2,3,4,5,6]	Already sorted input
[6,5,4,3,2,1]	Reverse sorted input

Edge Cases

One important edge case is when no triangle can be formed at all. Arrays such as [1, 1, 2] or [1, 2, 10] fail the triangle inequality theorem. A naive implementation might accidentally allow equality, but the condition must be strictly greater. The implementation correctly checks:

$a + b > c$

rather than >=.

Another important edge case occurs when the largest numbers do not form a triangle, but smaller numbers do. For example:

[3, 6, 2, 3]

After sorting:

[2,3,3,6]

The triplet (3,3,6) is invalid, but (2,3,3) is valid. The backward scan naturally handles this by continuing until a valid combination is found.

A third edge case involves repeated values. Arrays like [5,5,5,5] contain many identical side lengths. Some implementations mistakenly assume uniqueness or mishandle duplicates during sorting or iteration. This solution treats all elements independently, so repeated values work correctly.

Finally, arrays with exactly three elements require careful handling because there is only one possible triplet. The loop bounds in the implementation correctly allow the single candidate to be checked without causing index errors.