Largest Perimeter Triangle - Leetcode Solution

Problem: Given an array of positive integers A, find the largest perimeter of a triangle with non-zero area, formed by three of these lengths.

Solution:

The key to solving this problem is to understand the properties of a triangle. A triangle with sides a, b, and c can be formed if and only if the sum of any two sides is greater than the third side. Mathematically, this can be expressed as:

a + b > c a + c > b b + c > a

If we sort the array A in descending order, we can use the property above to check if we can form a triangle with the three largest elements in the array. If we can, we return the sum of the sides as the perimeter. If not, we move on to the next set of three largest elements until we have checked all possible triangles.

Algorithm:

1. Sort the input array A in descending order.
2. Initialize a variable max_perimeter to 0.
3. Loop through all possible triplets of elements in A. We start with the first three elements since we sorted in descending order.
4. Check if the triplet can form a triangle using the property above. If it can, calculate the perimeter and update max_perimeter if needed.
5. If we have checked all possible triplets and found no valid triangles, return 0.
6. Return max_perimeter.

Time Complexity: O(nlogn) - sorting the array takes nlogn time, and we loop through all possible triplets of elements in A, which takes O(n^3) time in the worst case.

Space Complexity: O(1) - we are not using any extra space.

Python Code:

class Solution:
    def largestPerimeter(self, A: List[int]) -> int:
        A.sort(reverse=True)
        max_perimeter = 0
        for i in range(len(A) - 2):
            a, b, c = A[i:i+3]
            if a < b + c:
                perimeter = a + b + c
                if perimeter > max_perimeter:
                    max_perimeter = perimeter
        return max_perimeter

Note: This problem can also be solved using a greedy approach. We can start by selecting the two largest elements in the array A, and try to find the largest possible third element that can form a non-zero area triangle with these two elements. We keep updating the selection of the two largest elements and the third element until we can no longer form a valid triangle. The time complexity of the greedy approach is O(n^2).

1