#976

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Largest Perimeter Triangle

Given an integer array, find the largest perimeter of a triangle formed from three of these lengths.

Problem Statement

Given an integer array nums, return the largest perimeter of a triangle formed from any three side lengths. A triangle is valid if the sum of the lengths of any two sides is greater than the third side. If no valid triangle can be formed, return 0.

For example, with nums = [2, 1, 2], you can form a triangle with sides 1, 2, and 2, resulting in a perimeter of 5. In contrast, with nums = [1, 2, 1, 10], no valid triangle can be formed, so the output is 0.

Examples

Example 1

Input: nums = [2,1,2]

Output: 5

You can form a triangle with three side lengths: 1, 2, and 2.

Example 2

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

Output: 0

You cannot use the side lengths 1, 1, and 2 to form a triangle. You cannot use the side lengths 1, 1, and 10 to form a triangle. You cannot use the side lengths 1, 2, and 10 to form a triangle. As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

Constraints

3 <= nums.length <= 104
1 <= nums[i] <= 106

Solution Approach

Sort the array

First, sort the array in descending order. This allows for checking the largest possible triangles first and ensures that the greedy choice of the largest values is always considered.

Check for a valid triangle

After sorting, check for any consecutive triplet of numbers in the sorted array that satisfies the triangle inequality: the sum of the first two sides must be greater than the third side. If this condition is met, return the perimeter of these three sides.

Return 0 if no triangle is valid

If no triplet satisfies the triangle inequality, return 0. This means it is impossible to form a triangle with the given side lengths.

Complexity Analysis

Metric	Value
Time	O(N \log N)
Space	O(1)

Sorting the array takes O(N log N) time, where N is the length of the array. Checking for a valid triangle after sorting takes O(1) for each triplet. Hence, the overall time complexity is O(N log N), and space complexity is O(1) because no additional space is required outside of the input array.

What Interviewers Usually Probe

Ability to recognize the greedy approach in problems involving optimization like this one.
Understanding of the triangle inequality and how it applies to the formation of valid triangles.
Efficient handling of sorting and triangle validation within the time complexity constraint.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check the triangle inequality after sorting the array.
Not considering the largest possible triangle first, leading to suboptimal solutions.
Overcomplicating the problem by not leveraging sorting to reduce unnecessary checks.

Follow-up variants

What if we allow more than one set of triangle sides to form? Could we maximize the sum of perimeters?
What if the array contains duplicate values? Does the approach still hold?
What if instead of maximizing the perimeter, we need to minimize it? How does this change the solution?

FAQ

What is the pattern for solving the Largest Perimeter Triangle problem?

The problem is best approached using greedy choice and invariant validation. After sorting the array, check consecutive triplets for the triangle inequality to find the largest valid perimeter.

Why do we sort the array in descending order?

Sorting in descending order allows you to check the largest possible triangles first, optimizing for the largest perimeter while ensuring a valid triangle.

What should we do if no valid triangle is found?

If no valid triangle can be formed from any triplet, return 0 as the perimeter.

How do we check if three sides can form a valid triangle?

For three sides a, b, and c, they form a valid triangle if a + b > c, b + c > a, and a + c > b.

What is the time complexity of this approach?

The time complexity is O(N log N) due to the sorting step, and the space complexity is O(1) because no additional data structures are used.

terminal

Solution

Solution 1: Sorting + Greedy

Suppose the three sides of the triangle are $a \leq b \leq c$. The triangle has non-zero area if and only if $a + b \gt c$.

1

2

3

4

5

6

7

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(len(nums) - 1, 1, -1):
            if (c := nums[i - 1] + nums[i - 2]) > nums[i]:
                return c + nums[i]
        return 0

Continue Practicing

#910 smallest range ii #1363 largest multiple of three #1561 maximum number of coins you can get