{x}
blog image

Largest Perimeter Triangle

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 <= 104
  • 1 <= nums[i] <= 106

Solution Explanation: Largest Perimeter Triangle

The problem asks to find the largest perimeter of a triangle that can be formed using three side lengths from a given array nums. A valid triangle must satisfy the triangle inequality theorem: the sum of the lengths of any two sides must be greater than the length of the third side.

The most efficient approach involves sorting and a greedy strategy.

Algorithm:

  1. Sort: Sort the input array nums in descending order. This ensures we consider the largest possible sides first.

  2. Iterate and Check: Iterate through the sorted array from the end (largest elements) to the beginning. For each triplet (a, b, c) where a >= b >= c, check if the triangle inequality holds (a < b + c).

  3. Return Perimeter: If the inequality holds for a triplet, it forms a valid triangle, and its perimeter (a + b + c) is returned as the largest possible perimeter.

  4. No Triangle: If the loop completes without finding a valid triangle, it means no such triangle exists, and 0 is returned.

Time Complexity Analysis:

  • Sorting: The dominant operation is sorting the input array nums, which takes O(n log n) time using efficient algorithms like merge sort or quicksort, where n is the length of nums.

  • Iteration and Check: The loop iterates at most n times, and each check within the loop takes constant O(1) time.

  • Overall: The overall time complexity is dominated by sorting, making it O(n log n).

Space Complexity Analysis:

  • In-place Sorting: Many sorting algorithms can be implemented in-place (without significant extra space).

  • Overall: The space complexity is O(1) (constant) for in-place sorting. If an in-place sorting algorithm is not used then it could be O(n) for the extra space required for sorting.

Code Examples (Python, Java, C++, and others):

The provided code snippets in Python, Java, C++, Go, TypeScript, Rust, and C all follow this algorithm. They differ slightly in syntax and specific libraries used for sorting, but the core logic remains the same. The Python example is detailed below for clarity.

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort(reverse=True)  # Sort in descending order
        for i in range(len(nums) - 2):  # Iterate through triplets
            a, b, c = nums[i], nums[i+1], nums[i+2]
            if a < b + c:  # Check triangle inequality
                return a + b + c  # Return perimeter
        return 0  # No valid triangle found

The other languages follow a very similar pattern, differing primarily in syntax for sorting and array manipulation. For instance, Java uses Arrays.sort(), C++ uses std::sort(), and so on. Each code snippet achieves the same algorithmic efficiency.