Largest Perimeter Triangle

Published: Oct 20, 2022

Introduction

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.

Constraints:

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

https://leetcode.com/problems/largest-perimeter-triangle/

Examples

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

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

Analysis

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.

Solution

class LargestPerimeterTriangle:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        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

Complexities

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