# Find Polygon With the Largest Perimeter
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-polygon-with-the-largest-perimeter)
Canonical: https://scaleengineer.com/dsa/problems/find-polygon-with-the-largest-perimeter
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Airtel](https://scaleengineer.com/companies/airtel)
---
## Problem
You are given an array of **positive** integers `nums` of length `n`.

A **polygon** is a closed plane figure that has at least `3` sides. The **longest side** of a polygon is **smaller** than the sum of its other sides.

Conversely, if you have `k` (`k >= 3`) **positive** real numbers `a1`, `a2`, `a3`, ..., `ak` where `a1 <= a2 <= a3 <= ... <= ak` **and** `a1 + a2 + a3 + ... + ak-1 > ak`, then there **always** exists a polygon with `k` sides whose lengths are `a1`, `a2`, `a3`, ..., `ak`.

The **perimeter** of a polygon is the sum of lengths of its sides.

Return _the **largest** possible **perimeter** of a **polygon** whose sides can be formed from_ `nums`, _or_ `-1` _if it is not possible to create a polygon_.

**Example 1:**

**Input:** nums = [5,5,5]
**Output:** 15
**Explanation:** The only possible polygon that can be made from nums has 3 sides: 5, 5, and 5. The perimeter is 5 + 5 + 5 = 15.

**Example 2:**

**Input:** nums = [1,12,1,2,5,50,3]
**Output:** 12
**Explanation:** The polygon with the largest perimeter which can be made from nums has 5 sides: 1, 1, 2, 3, and 5. The perimeter is 1 + 1 + 2 + 3 + 5 = 12.
We cannot have a polygon with either 12 or 50 as the longest side because it is not possible to include 2 or more smaller sides that have a greater sum than either of them.
It can be shown that the largest possible perimeter is 12.

**Example 3:**

**Input:** nums = [5,5,50]
**Output:** -1
**Explanation:** There is no possible way to form a polygon from nums, as a polygon has at least 3 sides and 50 > 5 + 5.

**Constraints:**

* `3 <= n <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute Force with Sorting
This approach involves sorting the array first. A sorted array simplifies checking the polygon condition, as the last element of any contiguous subarray is the largest. We then iterate through all possible contiguous subarrays ending at index `i` (from `n-1` down to `2`), checking if they form a valid polygon. Since we want the largest perimeter, we check the longest possible subarrays first. The first valid polygon found will have the largest perimeter.
**Time:** O(n^2). Sorting takes `O(n log n)`. The main logic is a nested loop. The outer loop runs about `n` times, and the inner loop runs up to `n` times, leading to `O(n^2)` operations. The total complexity is `O(n log n + n^2)`, which simplifies to `O(n^2)`. · **Space:** O(log n) or O(n). This space is used by the sorting algorithm. For instance, `Arrays.sort()` in Java for primitives uses a dual-pivot quicksort which has an average space complexity of `O(log n)`.
**Pros:** Relatively simple to conceptualize after sorting.; Guaranteed to find the correct answer if one exists.
**Cons:** The nested loop results in a quadratic time complexity, which is inefficient for large inputs.; Will likely be too slow and cause a Time Limit Exceeded error for constraints like n = 10^5.
### Explanation
The fundamental idea is that for a set of side lengths to form a polygon, the sum of the shorter sides must be strictly greater than the longest side. To maximize the perimeter, we should try to include as many sides as possible. By sorting the array `nums`, we can systematically check for valid polygons. We start by considering all `n` numbers, then `n-1` numbers, and so on. The first combination that satisfies the polygon property will yield the largest perimeter because we are reducing the total sum (by removing the largest elements) at each step. This approach implements this check by iterating from the end of the sorted array and, for each potential longest side `nums[i]`, summing up all preceding elements to check the condition. This leads to a nested loop structure.

```java
import java.util.Arrays;

class Solution {
    public long largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        // Iterate from the largest possible number of sides downwards
        for (int i = n - 1; i >= 2; i--) {
            // The sides considered are nums[0...i]
            // The longest side is nums[i]
            long sumOfOtherSides = 0;
            // Calculate sum of other sides
            for (int j = 0; j < i; j++) {
                sumOfOtherSides += nums[j];
            }
            
            // Check polygon condition
            if (sumOfOtherSides > nums[i]) {
                // Found the largest perimeter, return it
                return sumOfOtherSides + nums[i];
            }
        }
        
        // No valid polygon found
        return -1;
    }
}
```
### Algorithm
*   1. Sort the input array `nums` in non-decreasing order.
*   2. Iterate with an index `i` from `n-1` down to `2`. This `i` represents the index of the potential longest side in a polygon formed by sides `nums[0...i]`.
*   3. For each `i`, calculate the sum of all sides preceding `nums[i]`: `long sum = 0; for j from 0 to i-1, sum += nums[j]`.
*   4. Check if this `sum` is strictly greater than `nums[i]`.
*   5. If `sum > nums[i]`, a valid polygon is found. The perimeter is `sum + nums[i]`. Since we iterate from the largest `i` downwards, this is the largest possible perimeter. Return this value.
*   6. If the loop completes without finding a valid polygon, it means no polygon can be formed. Return -1.

## Greedy Approach with Prefix Sum Optimization
This is an optimized approach that builds upon sorting. Instead of re-calculating the sum of smaller sides in each iteration, we maintain a running sum. We start with the sum of all elements. Then, we iterate from the largest element downwards. If an element is too large to be the longest side of a polygon with the remaining elements, we discard it and subtract it from our running sum. This turns the check into an O(1) operation inside the loop.
**Time:** O(n log n). Sorting the array takes `O(n log n)`. The initial sum calculation takes `O(n)`. The subsequent loop runs at most `n` times with `O(1)` work inside. Therefore, the sorting step dominates the time complexity. · **Space:** O(log n) or O(n). Similar to the previous approach, this space is required by the sorting algorithm.
**Pros:** Optimal time complexity for the given constraints.; The greedy logic is sound and provides a clean and efficient solution.
**Cons:** The main performance bottleneck is the initial sorting step.
### Explanation
The greedy strategy is justified because to maximize the perimeter, we should use as many sides as possible from the given numbers. After sorting `nums`, we check if all `n` numbers can form a polygon. If `sum(nums[0]...nums[n-2]) > nums[n-1]`, then the sum of all numbers is the largest possible perimeter. If not, `nums[n-1]` is too long and can never be part of a valid polygon with any subset of the other numbers. Therefore, we must discard `nums[n-1]` and try to form a polygon with the remaining `n-1` numbers. This process is repeated. We can implement this efficiently by pre-calculating the total sum and then iterating from `i = n-1` down to `2`. In each step, we check the polygon condition. If it fails, we discard `nums[i]` by subtracting it from the total sum and continue. The first time the condition holds, we have found our answer.

```java
import java.util.Arrays;

class Solution {
    public long largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        
        long currentPerimeter = 0;
        for (int num : nums) {
            currentPerimeter += num;
        }
        
        for (int i = nums.length - 1; i >= 2; i--) {
            long longestSide = nums[i];
            // The sum of other sides is the current total perimeter minus the longest side.
            long sumOfOtherSides = currentPerimeter - longestSide;
            
            if (sumOfOtherSides > longestSide) {
                // We found the largest possible polygon.
                return currentPerimeter;
            } else {
                // This side is too long, it cannot be part of the polygon.
                // We discard it and try with the remaining smaller sides.
                currentPerimeter -= longestSide;
            }
        }
        
        return -1;
    }
}
```
### Algorithm
*   1. Sort the input array `nums` in non-decreasing order.
*   2. Calculate the initial sum of all elements in `nums` and store it in a `long` variable, say `currentPerimeter`.
*   3. Iterate with an index `i` from `n-1` down to `2`.
*   4. In each iteration, `nums[i]` is the candidate for the longest side. The sum of the other potential sides is `currentPerimeter - nums[i]`.
*   5. Check if `currentPerimeter - nums[i] > nums[i]`.
*   6. If the condition is true, a valid polygon is found with the largest possible perimeter, which is `currentPerimeter`. Return this value.
*   7. If the condition is false, `nums[i]` is too long. Discard it by updating `currentPerimeter = currentPerimeter - nums[i]`. Then, continue to the next iteration with a smaller set of sides.
*   8. If the loop finishes, no polygon can be formed. Return -1.

# Solutions
### Java

```java
class Solution {
public
  long largestPerimeter(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    long[] s = new long[n + 1];
    for (int i = 1; i <= n; ++i) {
      s[i] = s[i - 1] + nums[i - 1];
    }
    long ans = -1;
    for (int k = 3; k <= n; ++k) {
      if (s[k - 1] > nums[k - 1]) {
        ans = Math.max(ans, s[k]);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long largestPerimeter(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<long long> s(n + 1);
    for (int i = 1; i <= n; ++i) {
      s[i] = s[i - 1] + nums[i - 1];
    }
    long long ans = -1;
    for (int k = 3; k <= n; ++k) {
      if (s[k - 1] > nums[k - 1]) {
        ans = max(ans, s[k]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def largestPerimeter(self, nums: List[int]) -> int: nums . sort() s = list(accumulate(nums, initial=0)) ans = - 1 for k in range(3, len(nums) + 1): if s[k - 1] > nums[k - 1]: ans = max(ans, s[k]) return ans

```