# Largest Perimeter Triangle
**Difficulty:** EASY
[External](https://leetcode.com/problems/largest-perimeter-triangle)
Canonical: https://scaleengineer.com/dsa/problems/largest-perimeter-triangle
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Tesla](https://scaleengineer.com/companies/tesla)
---
## Problem
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`

# Approaches
## Brute Force with Three Nested Loops
This approach involves checking every possible combination of three side lengths from the input array. We use three nested loops to select three distinct numbers. For each combination, we check if they can form a valid triangle using the Triangle Inequality Theorem.
**Time:** O(n^3), where n is the number of elements in `nums`. This is because of the three nested loops required to check every combination of three sides. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs.
**Cons:** Very inefficient due to its cubic time complexity.; Will likely result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The Triangle Inequality Theorem states that for three side lengths `a`, `b`, and `c` to form a triangle, the sum of the lengths of any two sides must be greater than the length of the third side (`a + b > c`, `a + c > b`, and `b + c > a`).

The algorithm proceeds as follows:
1. Initialize a variable `maxPerimeter` to 0.
2. Use three nested loops to pick three distinct indices `i`, `j`, and `k` from the array.
3. For each triplet of numbers `(nums[i], nums[j], nums[k])`, check if they satisfy all three conditions of the triangle inequality.
4. If they form a valid triangle, calculate their sum (perimeter) and update `maxPerimeter` if this new perimeter is larger than the current `maxPerimeter`.
5. After checking all possible triplets, the value stored in `maxPerimeter` is the answer. If no triangle could be formed, it will remain 0.

```java
class Solution {
    public int largestPerimeter(int[] nums) {
        int n = nums.length;
        int maxPerimeter = 0;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    int a = nums[i];
                    int b = nums[j];
                    int c = nums[k];
                    if (a + b > c && a + c > b && b + c > a) {
                        maxPerimeter = Math.max(maxPerimeter, a + b + c);
                    }
                }
            }
        }
        return maxPerimeter;
    }
}
```
### Algorithm
- Initialize `maxPerimeter` to 0.
- Use three nested loops to iterate through all unique triplets `(i, j, k)`.
- Let the sides be `a = nums[i]`, `b = nums[j]`, `c = nums[k]`.
- Check if `a`, `b`, and `c` can form a valid triangle using the triangle inequality: `a + b > c`, `a + c > b`, and `b + c > a`.
- If they form a valid triangle, update `maxPerimeter = max(maxPerimeter, a + b + c)`.
- Return `maxPerimeter` after the loops complete.

## Sorting and Greedy Approach
A much more efficient approach is to first sort the array. To maximize the perimeter, we should use the largest possible side lengths. By sorting the array, we can simplify the triangle check and greedily search for the largest perimeter triangle starting from the largest elements.
**Time:** O(n log n), where n is the number of elements in `nums`. The sorting operation takes O(n log n) time, and the subsequent linear scan takes O(n) time. · **Space:** O(log n) or O(n), depending on the space complexity of the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort, which has an average space complexity of O(log n).
**Pros:** Highly efficient and optimal solution.; Simple logic after sorting.; The greedy choice of checking the largest elements first is guaranteed to find the maximum perimeter.
**Cons:** The time complexity is bound by the sorting algorithm.
### Explanation
The key insight is based on the Triangle Inequality Theorem. If we have three side lengths `a`, `b`, and `c` such that `a <= b <= c`, we only need to check if `a + b > c`. The other two inequalities (`a + c > b` and `b + c > a`) will always hold true since `c` is the largest side.

To find the largest perimeter, we should prioritize using the largest numbers available. This leads to a greedy strategy.

The algorithm is as follows:
1. Sort the input array `nums` in non-decreasing order.
2. Iterate backwards from the end of the sorted array, from index `i = n-1` down to `2`.
3. In each iteration, consider the triplet of sides `(nums[i-2], nums[i-1], nums[i])`. These are three consecutive elements.
4. Check if they form a valid triangle. Since the array is sorted, `nums[i-2] <= nums[i-1] <= nums[i]`. We only need to check if `nums[i-2] + nums[i-1] > nums[i]`.
5. If this condition is true, we have found a valid triangle. Because we are iterating from the largest elements downwards, this must be the triangle with the largest possible perimeter. Any other valid triangle would involve smaller sides, resulting in a smaller perimeter. We can immediately return the perimeter `nums[i-2] + nums[i-1] + nums[i]`.
6. If the loop completes without finding any such triplet, it means no valid triangle can be formed. In this case, we return 0.

```java
import java.util.Arrays;

class Solution {
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 2; i--) {
            // Let nums[i] be the longest side 'c'
            // Let nums[i-1] be 'b' and nums[i-2] be 'a'
            // Since the array is sorted, a <= b <= c.
            // We only need to check if a + b > c.
            if (nums[i - 2] + nums[i - 1] > nums[i]) {
                return nums[i - 2] + nums[i - 1] + nums[i];
            }
        }
        return 0;
    }
}
```
### Algorithm
- Sort the input array `nums` in ascending order.
- Iterate backwards from `i = n-1` down to `2`.
- For each `i`, consider the triplet `(nums[i-2], nums[i-1], nums[i])`.
- Check if `nums[i-2] + nums[i-1] > nums[i]`.
- If the condition is true, this triplet forms the largest possible perimeter triangle. Return `nums[i-2] + nums[i-1] + nums[i]`.
- If the loop finishes, no valid triangle can be formed. Return `0`.

# Solutions
### Java

```java
class Solution { public int largestPerimeter ( int [] nums ) { Arrays . sort ( nums ); for ( int i = nums . length - 1 ; i >= 2 ; -- i ) { int c = nums [ i - 1 ] + nums [ i - 2 ]; if ( c > nums [ i ]) { return c + nums [ i ]; } } return 0 ; } }
```

### CPP

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

### Python

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