Find Polygon With the Largest Perimeter - LeetCode Daily Challenge

Problem Statement

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.

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public long largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        long previousElementsSum = 0;
        long ans = -1;
        for (int num : nums) {
            if (num < previousElementsSum) {
                ans = num + previousElementsSum;
            }
            previousElementsSum += num;
        }
        return ans;
    }
}

C++ Code

class Solution {
public:
    long long largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        long long previousElementsSum = 0;
        long long ans = -1;
        for (int num : nums) {
            if (num < previousElementsSum) {
                ans = num + previousElementsSum;
            }
            previousElementsSum += num;
        }
        return ans;
    }
};

Python Code

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        previous_elements_sum = 0
        ans = -1
        for num in nums:
            if num < previous_elements_sum:
                ans = num + previous_elements_sum
            previous_elements_sum += num
        return ans

Javascript Code

var largestPerimeter = function(nums) {
    nums.sort((a, b) => a - b);
    let previousElementsSum = 0;
    let ans = -1;
    for (let num of nums) {
        if (num < previousElementsSum) {
            ans = num + previousElementsSum;
        }
        previousElementsSum += num;
    }
    return ans;
};

Go Code

func largestPerimeter(nums []int) int64 {
    sort.Ints(nums)
    var previousElementsSum int64 = 0
    var ans int64 = -1
    for _, num := range nums {
        if int64(num) < previousElementsSum {
            ans = int64(num) + previousElementsSum
        }
        previousElementsSum += int64(num)
    }
    return ans
}

Complexity Analysis

Time Complexity: O(N * logN)
Space complexity: O(N) or O(log⁡N). Some extra space is used when we sort an array of size N in place. The space complexity of the sorting algorithm depends on the programming language.