2971. Find Polygon With the Largest Perimeter LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2971. Find Polygon With the Largest Perimeter LeetCode Solution with the best time and space complexity. The solution to Find Polygon With the Largest Perimeter problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find Polygon With the Largest Perimeter solution in C++
Find Polygon With the Largest Perimeter solution in Java
Find Polygon With the Largest Perimeter solution in Python
Additional Resources

2971. Find Polygon With the Largest Perimeter LeetCode Solution image

Problem Statement of Find Polygon With the Largest Perimeter

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, 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

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})

2971. Find Polygon With the Largest Perimeter LeetCode Solution in C++

class Solution {
 public:
  long long largestPerimeter(vector<int>& nums) {
    long prefix = accumulate(nums.begin(), nums.end(), 0L);

    ranges::sort(nums);

    for (int i = nums.size() - 1; i >= 2; --i) {
      prefix -= nums[i];
      // Let nums[i] be the longest side. Check if the sum of all the edges with
      // length no longer than nums[i] > nums[i].
      if (prefix > nums[i])
        return prefix + nums[i];
    }

    return -1;
  }
};
/* code provided by PROGIEZ */

2971. Find Polygon With the Largest Perimeter LeetCode Solution in Java

class Solution {
  public long largestPerimeter(int[] nums) {
    long prefix = Arrays.stream(nums).asLongStream().sum();

    Arrays.sort(nums);

    for (int i = nums.length - 1; i >= 2; --i) {
      prefix -= nums[i];
      // Let nums[i] be the longest side. Check if the sum of all the edges with
      // length no longer than nums[i] > nums[i].
      if (prefix > nums[i])
        return prefix + nums[i];
    }

    return -1;
  }
}
// code provided by PROGIEZ

2971. Find Polygon With the Largest Perimeter LeetCode Solution in Python

class Solution:
  def largestPerimeter(self, nums: list[int]) -> int:
    prefix = sum(nums)

    for num in sorted(nums, reverse=True):
      prefix -= num
      # Let `num` be the longest side. Check if the sum of all the edges with
      # length no longer than `num` > `num``.
      if prefix > num:
        return prefix + num

    return -1
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents