# LeetCode 976: Largest Perimeter Triangle

## Problem Restatement

We are given an integer array `nums`.

Each number represents a possible side length of a triangle.

We need to choose three lengths that can form a triangle with non-zero area. Among all valid choices, return the largest possible perimeter.

If no three lengths can form a valid triangle, return `0`.

A valid triangle with side lengths `a`, `b`, and `c` must satisfy the triangle inequality. If the sides are sorted so that:

```python
a <= b <= c
```

then we only need to check:

```python
a + b > c
```

The official constraints are `3 <= nums.length <= 10^4` and `1 <= nums[i] <= 10^6`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | The largest possible perimeter of a valid triangle |
| Invalid case | Return `0` if no valid triangle exists |
| Key condition | For sorted sides `a <= b <= c`, require `a + b > c` |

Function shape:

```python
def largestPerimeter(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [2, 1, 2]
```

After sorting:

```python
[1, 2, 2]
```

Check the three sides:

```python
1 + 2 > 2
```

This is true, so these sides form a valid triangle.

The perimeter is:

```python
1 + 2 + 2 = 5
```

Answer:

```python
5
```

Example 2:

```python
nums = [1, 2, 1, 10]
```

After sorting:

```python
[1, 1, 2, 10]
```

Check the largest three values:

```python
1 + 2 > 10
```

False.

Check the next three values:

```python
1 + 1 > 2
```

False.

No valid triangle exists.

Answer:

```python
0
```

## First Thought: Brute Force

The direct solution is to try every group of three numbers.

For every triple `(i, j, k)`, compute the side lengths and check whether they form a valid triangle.

If they do, compute the perimeter and keep the maximum.

```python
class Solution:
    def largestPerimeter(self, nums: list[int]) -> int:
        n = len(nums)
        best = 0

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    sides = sorted([nums[i], nums[j], nums[k]])
                    a, b, c = sides

                    if a + b > c:
                        best = max(best, a + b + c)

        return best
```

This checks all possible triples, so it is correct.

## Problem With Brute Force

The brute force solution checks `O(n^3)` triples.

Since `nums.length` can be as large as `10^4`, this is too slow.

We need to avoid enumerating every combination.

## Key Insight

To maximize the perimeter, we want large side lengths.

So we sort the array.

Then we inspect triples from largest to smallest.

After sorting:

```python
nums.sort()
```

For any three sides:

```python
a <= b <= c
```

the only condition we need to check is:

```python
a + b > c
```

The other two inequalities are automatically true because `c` is already the largest side.

Now consider a sorted array.

For a fixed largest side `nums[i]`, the best possible two smaller sides are:

```python
nums[i - 2], nums[i - 1]
```

They are the two largest values before `nums[i]`.

If these two cannot form a triangle with `nums[i]`, then no smaller pair can form a triangle with `nums[i]`.

So we only need to check consecutive triples from right to left.

## Algorithm

Sort `nums` in ascending order.

Start from the last index and check each triple:

```python
nums[i - 2], nums[i - 1], nums[i]
```

For each triple:

1. Let `a = nums[i - 2]`.
2. Let `b = nums[i - 1]`.
3. Let `c = nums[i]`.
4. If `a + b > c`, return `a + b + c`.
5. Otherwise, move left and try the next triple.

If no valid triple is found, return `0`.

## Correctness

After sorting, every checked triple has the form:

```python
a <= b <= c
```

For such a triple, the triangle has non-zero area exactly when:

```python
a + b > c
```

The algorithm checks triples from the largest possible side lengths down to smaller ones.

When it checks index `i`, the values `nums[i - 2]` and `nums[i - 1]` are the two largest available values smaller than or equal to `nums[i]`.

If:

```python
nums[i - 2] + nums[i - 1] <= nums[i]
```

then any other pair before `i` has a sum less than or equal to that sum, so no pair with `nums[i]` can form a valid triangle.

If:

```python
nums[i - 2] + nums[i - 1] > nums[i]
```

then the triple is valid.

Because we scan from the largest values downward, the first valid triple has the largest possible perimeter. Returning it is correct.

If the scan finishes without finding a valid triple, then no valid triangle can be formed, so returning `0` is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Sorting dominates the runtime |
| Space | `O(1)` | The scan uses constant extra space, ignoring sort internals |

## Implementation

```python
class Solution:
    def largestPerimeter(self, nums: list[int]) -> int:
        nums.sort()

        for i in range(len(nums) - 1, 1, -1):
            a = nums[i - 2]
            b = nums[i - 1]
            c = nums[i]

            if a + b > c:
                return a + b + c

        return 0
```

## Code Explanation

We first sort the side lengths:

```python
nums.sort()
```

This lets us reason about each triple as:

```python
a <= b <= c
```

Then we scan from the end:

```python
for i in range(len(nums) - 1, 1, -1):
```

At each position, `nums[i]` is the largest side in the current triple.

The two sides before it are the largest possible companions:

```python
a = nums[i - 2]
b = nums[i - 1]
c = nums[i]
```

We check the triangle inequality:

```python
if a + b > c:
```

If true, we return the perimeter:

```python
return a + b + c
```

If no triple passes the check, no valid triangle exists:

```python
return 0
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.largestPerimeter([2, 1, 2]) == 5
    assert s.largestPerimeter([1, 2, 1, 10]) == 0
    assert s.largestPerimeter([3, 2, 3, 4]) == 10
    assert s.largestPerimeter([3, 6, 2, 3]) == 8
    assert s.largestPerimeter([1, 1, 2]) == 0
    assert s.largestPerimeter([5, 5, 5]) == 15

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[2, 1, 2]` | `5` | Basic valid triangle |
| `[1, 2, 1, 10]` | `0` | No valid triangle |
| `[3, 2, 3, 4]` | `10` | Best triangle is `3, 3, 4` |
| `[3, 6, 2, 3]` | `8` | Largest values fail first, smaller triple works |
| `[1, 1, 2]` | `0` | Degenerate triangle has zero area |
| `[5, 5, 5]` | `15` | Equal sides form a valid triangle |