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 thelargest possible perimeter of a polygon whose sides can be formed from nums, or -1 if it is not possible to create a polygon.

Examples

Example 1

1
2
3

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

1
2
3
4
5

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

1
2
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 <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Greedy with Sorting and Prefix Sum

Intuition

To form a polygon, the sum of all sides except the largest must be greater than the largest side. To maximize the perimeter, we sort the array and try to use as many largest sides as possible, checking the polygon condition from the largest possible subset down to 3 sides.

Approach

  1. Sort nums in non-decreasing order.
  2. Compute the prefix sum of nums for efficient range sum queries.
  3. For k from n down to 3:
    • If the sum of the first k-1 elements is greater than the kth element, return the sum of the first k elements as the answer.
  4. If no such k exists, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    long long largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<long long> pre(n+1);
        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + nums[i];
        for (int k = n; k >= 3; --k) {
            if (pre[k-1] > nums[k-1]) return pre[k];
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func largestPerimeter(nums []int) int64 {
    sort.Ints(nums)
    n := len(nums)
    pre := make([]int64, n+1)
    for i := 0; i < n; i++ {
        pre[i+1] = pre[i] + int64(nums[i])
    }
    for k := n; k >= 3; k-- {
        if pre[k-1] > int64(nums[k-1]) {
            return pre[k]
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public long largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        long[] pre = new long[n+1];
        for (int i = 0; i < n; i++) pre[i+1] = pre[i] + nums[i];
        for (int k = n; k >= 3; k--) {
            if (pre[k-1] > nums[k-1]) return pre[k];
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun largestPerimeter(nums: IntArray): Long {
        nums.sort()
        val n = nums.size
        val pre = LongArray(n+1)
        for (i in 0 until n) pre[i+1] = pre[i] + nums[i]
        for (k in n downTo 3) {
            if (pre[k-1] > nums[k-1]) return pre[k]
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def largestPerimeter(self, nums: list[int]) -> int:
        nums.sort()
        pre = [0]
        for x in nums:
            pre.append(pre[-1] + x)
        for k in range(len(nums), 2, -1):
            if pre[k-1] > nums[k-1]:
                return pre[k]
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn largest_perimeter(nums: Vec<i32>) -> i64 {
        let mut nums = nums;
        nums.sort();
        let n = nums.len();
        let mut pre = vec![0i64; n+1];
        for i in 0..n {
            pre[i+1] = pre[i] + nums[i] as i64;
        }
        for k in (3..=n).rev() {
            if pre[k-1] > nums[k-1] as i64 {
                return pre[k];
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    largestPerimeter(nums: number[]): number {
        nums.sort((a, b) => a - b);
        const n = nums.length;
        const pre: number[] = [0];
        for (let i = 0; i < n; i++) pre.push(pre[pre.length-1] + nums[i]);
        for (let k = n; k >= 3; k--) {
            if (pre[k-1] > nums[k-1]) return pre[k];
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the length of nums, due to sorting.
  • 🧺 Space complexity: O(n), for the prefix sum array.