Largest Perimeter Triangle

Difficulty: Easy | Acceptance: 62.20% | Paid: No Topics: Array, Math, Greedy, Sorting

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Sorting and Greedy

Examples

Example 1:

Input: nums = [2,1,2]
Output: 5
Explanation: You can form a triangle with three side lengths: 1, 2, and 2.

Example 2:

Input: nums = [1,2,1]
Output: 0
Explanation: You cannot form a triangle with the given values.

Constraints

- 3 <= nums.length <= 10^4
- 1 <= nums[i] <= 10^6

Approach 1: Brute Force

Intuition Check every possible combination of three sides in the array to see if they can form a valid triangle, keeping track of the maximum perimeter found.

Steps

• Initialize a variable max_perimeter to 0.
• Use three nested loops to iterate through all unique triplets (i, j, k) where i < j < k.
• For each triplet, check the triangle inequality theorem: a + b > c, a + c > b, and b + c > a.
• If the triplet forms a valid triangle, update max_perimeter with the maximum of its current value and the sum of the triplet.
• Return max_perimeter.

class Solution:
    def largestPerimeter(self, nums: list[int]) -> int:
        n = len(nums)
        max_perimeter = 0
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    a, b, c = nums[i], nums[j], nums[k]
                    if a + b > c and a + c > b and b + c > a:
                        max_perimeter = max(max_perimeter, a + b + c)
        return max_perimeter

Complexity

• Time: O(n³) - We iterate through all possible triplets.
• Space: O(1) - We only use a few variables for storage.
• Notes: This approach is inefficient for large inputs (n up to 10⁴) and will likely result in a Time Limit Exceeded error.

Approach 2: Sorting and Greedy

Intuition To maximize the perimeter, we should prioritize the largest numbers. If we sort the array in ascending order, we can efficiently check the largest valid triplet. For three sorted sides a <= b <= c, the condition a + b > c is sufficient to form a triangle (since c + a > b and c + b > a are implicitly true).

Steps

• Sort the array nums in ascending order.
• Iterate from the end of the array towards the beginning (index i from n-1 down to 2).
• For each index i, check if nums[i-2] + nums[i-1] > nums[i].
• If the condition is true, these three sides form the triangle with the largest possible perimeter (because we are checking from the largest sides downwards). Return their sum.
• If the loop finishes without finding a valid triangle, return 0.

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

Complexity

• Time: O(n log n) - Dominated by the sorting step.
• Space: O(1) or O(n) - Depending on the sorting algorithm’s space complexity (e.g., log n stack space for quicksort, or n for mergesort).
• Notes: This is the optimal approach for this problem.