Largest Perimeter Triangle

To find the largest perimeter of a triangle from an array, we need to follow the triangle inequality theorem which states that the sum of the lengths of any two sides of a triangle must be greater than or equal to the length of the third side.

Given this, we should first sort the array in decreasing order. We then iterate over the array and check if the current element and the two elements after it form a valid triangle (i.e., whether the sum of the two smaller numbers is greater than the largest number). If they do, we return their sum, which will be the largest possible perimeter, because we are starting from the largest side lengths due to sorting.

Python solution:

1
2
3
4
5
6
7

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

This has a time complexity of O(n log n) due to the sorting operation, where n is the length of the input array. The space complexity is O(1) as we are not using any additional space that scales with input size.

The triangle inequality theorem is expressed in the code on the following line:

1

if nums[i] < nums[i + 1] + nums[i + 2]:

This line checks if the sum of the lengths of the two smaller sides (nums[i + 1] and nums[i + 2] since the array is sorted in descending order) is greater than the length of the potential largest side (nums[i]). If this condition is true, then these three sides can form a triangle according to the triangle inequality theorem.

In this problem, the invariant is the triangle inequality theorem, which states that the sum of the lengths of any two sides of a triangle must be greater than the length of the third side.

This theorem is used as an invariant in the loop to continuously check whether three consecutive numbers in the sorted array can form a triangle. It remains true and is consistently relied upon throughout the loop, which makes it an invariant in the context of this problem.

The loop invariant in this problem is the condition checked in the loop, which is: for any three consecutive numbers in the sorted array (nums[i], nums[i+1], nums[i+2]), nums[i] + nums[i+1] > nums[i+2].

This condition, if true, means that these three numbers can form a triangle. As the array is sorted in descending order, if these three numbers can form a triangle, they will have the largest possible perimeter.

The loop invariant is important for the correctness of the algorithm because it guides the loop to continue or break based on whether the current three numbers meet the triangle inequality theorem, ensuring the loop will eventually find the largest possible triangle perimeter or determine that no triangle can be formed.

We need to sort the list of sides to be able to effectively apply the triangle inequality theorem which states that the sum of lengths of any two sides of a triangle must be greater than the length of the remaining side.

When the list is sorted in descending order, we can iterate through the list and for each set of three sides (nums[i], nums[i+1], nums[i+2]), we know that nums[i] is the largest. Therefore, we only need to check if nums[i+1] + nums[i+2] > nums[i].

If this condition is true, we know that these three numbers can form a triangle and since our list is sorted in descending order, we can immediately return the sum as the largest perimeter.

If we didn’t sort the list, we would have to check the condition for all possible combinations of three sides, which would be more time-consuming and complex.