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.
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,10] Output: 0 Explanation: 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 <= 1041 <= nums[i] <= 106The idea is to sort the array in non-decreasing order and try to form the triangle starting from the largest possible sides. If the largest sides satisfy the triangle inequality, they will produce the largest perimeter. Iterate from the end of the sorted array and check for the triangle inequality condition for the last three elements. If the condition is satisfied, those three can form a triangle, otherwise keep checking the next set of three largest sides.
This Python function begins by sorting the input array. It then iterates backward from the third last element, checking if the current element and the next two largest elements can form a triangle using the triangle inequality rule. If they can, it returns their sum as the largest perimeter.
C
Java
C++
C#
JavaScript
Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(1) as no additional space is used apart from auxiliary variables.
This approach involves checking all possible combinations of three lengths from the array to see if they form a triangle. If they do, we calculate the perimeter and update the maximum perimeter found so far. This approach is less efficient due to its combinatorial nature but demonstrates the basic principle of checking all potential solutions.
This Python brute force solution checks every triplet of indices to see if they can form a triangle by satisfying the triangle inequality. If they can, it potentially updates the maximum perimeter result.
C
Java
C++
C#
JavaScript
Time Complexity: O(n^3), as it evaluates all combinations of three elements. Space Complexity: O(1), requiring constant additional space.
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(1) as no additional space is used apart from auxiliary variables. |
| Brute Force Approach | Time Complexity: O(n^3), as it evaluates all combinations of three elements. Space Complexity: O(1), requiring constant additional space. |
Find Polygon with the Largest Perimeter - Leetcode 2971 - Python • NeetCodeIO • 13,403 views views
Watch 9 more video solutions →Practice Largest Perimeter Triangle with our built-in code editor and test cases.
Practice on FleetCode