Problem Description

Given an array of positive integers nums where each element represents the length of a side of a triangle, your task is to find the largest perimeter of a triangle with a non-zero area that can be formed from three of these lengths. If no such triangle can be formed, return 0.

• You must use exactly three different elements from nums for the triangle sides.
• You cannot reuse the same element index for multiple sides.
• The triangle must have a non-zero area, so the triangle inequality must be satisfied: for any three sides a, b, c, the sum of any two sides must be greater than the third.
• Return the largest possible perimeter, or 0 if no valid triangle exists.

Thought Process

At first glance, the most straightforward way to solve this problem is to try every possible combination of three sides and check if they can form a triangle. For each valid triangle, we could compute its perimeter and keep track of the largest one found.

However, this brute-force approach is inefficient, especially for large arrays, because the number of combinations grows quickly. To optimize, we should recall the triangle inequality: for three lengths a, b, and c (where a ≤ b ≤ c), a triangle is possible if and only if a + b > c.

Since we want the largest perimeter, it's logical to try the largest sides first. If the largest three lengths can't form a triangle, then no other smaller combination can yield a larger perimeter. This insight leads us to consider sorting the array and checking combinations from largest to smallest.

Solution Approach

• Step 1: Sort the array in descending order.
  • This allows us to check the largest possible sides first, maximizing the perimeter.
• Step 2: Iterate through the array, considering every triplet of consecutive elements.
  • For each triplet (a, b, c) (where a ≥ b ≥ c), check if b + c > a.
  • If this condition is true, the sides can form a triangle, and their sum is the largest possible perimeter for this input.
• Step 3: Return the perimeter of the first valid triangle found.
  • If no valid triangle exists, return 0.

This approach is efficient because sorting takes O(n \log n) time, and checking each triplet is O(n). We only need to check consecutive triplets because, after sorting, any larger perimeter would require larger sides, which we've already considered.

Example Walkthrough

Let's consider the example input: nums = [2, 1, 2].

1. Sort the array in descending order: [2, 2, 1].
2. Check the first (and only) triplet: 2, 2, 1.
   • Check if 2 + 1 > 2 → 3 > 2 (True).
   • Since the condition is satisfied, the perimeter is 2 + 2 + 1 = 5.
3. Return 5 as the answer.

If the input was [1, 2, 1], sorting gives [2, 1, 1]. Here, 1 + 1 > 2 is not true, so no triangle can be formed, and the function returns 0.

Time and Space Complexity

• Brute-force approach:
  • Time: O(n^3) (checking all triplets).
  • Space: O(1) (no extra space needed).
• Optimized approach (sorting and scanning):
  • Time: O(n \log n) for sorting + O(n) for scanning = O(n \log n) overall.
  • Space: O(1) if sorting in-place, or O(n) if not.

The optimized approach is much more efficient and is suitable for large input sizes.

Summary

To solve the Largest Perimeter Triangle problem, we leveraged the triangle inequality and the desire to maximize the perimeter. By sorting the side lengths and checking only consecutive triplets from largest to smallest, we ensure both correctness and efficiency. This method avoids unnecessary checks and quickly finds the largest possible perimeter or correctly determines when no valid triangle exists.

Code Implementation

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

class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        sort(nums.rbegin(), nums.rend());
        for (int i = 0; i < nums.size() - 2; ++i) {
            if (nums[i+1] + nums[i+2] > nums[i]) {
                return nums[i] + nums[i+1] + nums[i+2];
            }
        }
        return 0;
    }
};
      

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int largestPerimeter(int[] nums) {
        Integer[] arr = Arrays.stream(nums).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, Collections.reverseOrder());
        for (int i = 0; i < arr.length - 2; i++) {
            if (arr[i+1] + arr[i+2] > arr[i]) {
                return arr[i] + arr[i+1] + arr[i+2];
            }
        }
        return 0;
    }
}
      

var largestPerimeter = function(nums) {
    nums.sort((a, b) => b - a);
    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i+1] + nums[i+2] > nums[i]) {
            return nums[i] + nums[i+1] + nums[i+2];
        }
    }
    return 0;
};