Largest Perimeter Triangle

Published: Oct 20, 2022

Easy Math Sorting Greedy


This problem requires a bit of trigonometry knowledge. To form a triangle, 3 sides a, b, c should have the length, a + b > c, where c is the longest side. Sort the given array, then find 3 largest values which satisfy the condition.

Problem Description

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.


  • 3 <= nums.length <= 10**4
  • 1 <= nums[i] <= 10**6


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


The first step is to sort the given array. The examples show an array of just 3 elements, but as in the constraints, the array is much longer. To find 3 sides, shift 3 values one by one. This is because a + b > c is a condition. If the current longest doesn’t satisfy the condition, the longest should be switched to the next longest. Without changing the longest c, changing a or b might work. However, a + b + c must be the largest. So, shifting values one by one gives us the answer.


class LargestPerimeterTriangle:
    def largestPerimeter(self, nums: List[int]) -> int:
        for i in range(len(nums) - 3, -1, -1):
            if nums[i] + nums[i + 1] > nums[i + 2]:
                return nums[i] + nums[i + 1] + nums[i + 2]
        return 0


  • Time: O(nlog(n))
  • Space: O(1)