Largest Perimeter Triangle

Problem Statement

Given an array of integers named nums, which represents possible lengths of sides of a triangle, the task is to determine the largest possible perimeter of a triangle that has a non-zero area, using any three side lengths from the array. If it is not feasible to form a triangle that meets the non-zero area condition with any combination of three side lengths from the array, the function should return 0.

The formation of a triangle with a non-zero area is bound by 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.

Examples

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

Approach and Intuition

To find the largest perimeter of a triangle that can be formed with a non-zero area, follow these steps:

1. First, sort the array nums in ascending order to make it easier to check combinations of sides.

2. Starting from the largest possible sides (as they would give the largest perimeter), iterate through the sorted array from end to start.

3. For each triplet of adjacent sides in the sorted list, check if they can form a valid triangle using the triangle inequality theorem. Specifically, for any triplet (a, b, c) where a <= b <= c, check if a + b > c. This would imply that a triangle can be formed with a, b, and c as side lengths.

4. As soon as a valid triplet is found, the perimeter of the triangle can be calculated as a + b + c and returned because this is the largest perimeter that can be achieved due to the sorted order of elements.

5. If no valid triplet is found by the end of the loop, return 0.

Using the above steps, the approach efficiently finds the largest possible perimeter of a triangle by prioritizing the largest side lengths first and ensuring that each triplet forming the sides of a triangle meets the triangle inequality theorem to return a valid non-zero area.

Solutions

class Solution {
    public int maxPerimeter(int[] nums) {
        Arrays.sort(nums);
        for (int j = nums.length - 3; j >= 0; --j)
            if (nums[j] + nums[j+1] > nums[j+2])
                return nums[j] + nums[j+1] + nums[j+2];
        return 0;
    }
}