Leetcode 2971: Find Polygon With the Largest Perimeter

Input: The input consists of an array `nums` of positive integers. The task is to determine the largest possible perimeter of a polygon that can be made from the elements in `nums`.

Example: nums = [4, 6, 7, 3]

Constraints:

• 3 <= n <= 10^5

• 1 <= nums[i] <= 10^9

Output: Return the largest possible perimeter of a polygon that can be formed using the elements in `nums`, or return `-1` if no valid polygon can be made.

Example: Output: 17

Constraints:

Goal: The goal is to find the largest possible perimeter of a polygon formed by the sides in `nums`. The key condition is that the sum of the lengths of any `k-1` sides must be greater than the length of the remaining side.

Steps:

• Sort the array `nums` in ascending order.

• Iterate through the array from the largest element and check if the sum of all elements smaller than the current element is greater than the current element.

• If the condition is met, return the sum of the elements that form the polygon (perimeter).

• If no valid polygon can be formed, return -1.

Goal: The array has at least three integers, and the values of `nums[i]` range from 1 to 10^9. The task is to determine the largest possible perimeter from the elements in `nums`.

Steps:

• 3 <= n <= 10^5

• 1 <= nums[i] <= 10^9

Assumptions:

• The array is guaranteed to have at least three integers, as this is a requirement for forming a polygon.

• All elements in the array are positive integers.

• Input: Input: nums = [4, 6, 7, 3]

• Explanation: The array is sorted as [3, 4, 6, 7]. We can form a polygon with sides 3, 4, 6, and 7. The sum of the sides is 17, which is the largest perimeter that can be formed.

• Input: Input: nums = [8, 10, 2, 1, 5, 7]

• Explanation: The sorted array is [1, 2, 5, 7, 8, 10]. A polygon can be formed with sides 1, 2, 5, 7, and 10. The perimeter is 25.

• Input: Input: nums = [10, 20, 30]

• Explanation: The sorted array is [10, 20, 30]. We cannot form a polygon because the longest side 30 is greater than the sum of the other two sides (10 + 20).

Approach: Sort the array `nums` and iterate through the elements to check if a valid polygon can be formed. If the condition for the polygon is met, return the perimeter; otherwise, return -1.

Observations:

• We need to find the largest possible perimeter, so sorting the array in ascending order helps to check if the largest side is smaller than the sum of the others.

• The sorting helps efficiently check if the sum of any `k-1` sides is greater than the largest side.

Steps:

• Sort the array `nums` in ascending order.

• Start from the largest element and check if the sum of the smaller elements is greater than the current element.

• If the condition holds, return the sum of the elements in the valid polygon.

• If no valid polygon can be formed, return -1.

Empty Inputs:

• There will always be at least three elements in `nums`, as per the constraints.

Large Inputs:

• The array can contain up to 10^5 elements, so the solution must handle large inputs efficiently.

Special Values:

• Ensure that the largest side is not greater than the sum of the other sides for a valid polygon.

Constraints:

• The array must have at least three elements, and all elements are positive integers.

long long largestPerimeter(vector<int>& nums) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    vector<long long> sum(n, 0);
    sum[0] = nums[0];
    for(int i = 1; i < n; i++) sum[i] = sum[i - 1] + nums[i];
    for(int i = n - 1; i >= 2; i--)
        if(nums[i] < sum[i - 1])
            return sum[i];
    return -1;
}

1 : Function Definition

long long largestPerimeter(vector<int>& nums) {

Defines the function `largestPerimeter` that takes a reference to an integer array `nums` and returns a long long value representing the largest valid perimeter of a triangle that can be formed.

2 : Variable Initialization

    int n = nums.size();

Initializes the variable `n` to store the size of the input array `nums`.

3 : Sorting

    sort(nums.begin(), nums.end());

Sorts the array `nums` in ascending order to ensure that the largest sides come at the end for easier comparison.

4 : Cumulative Sum Calculation

    vector<long long> sum(n, 0);

Initializes a vector `sum` to store the cumulative sums of the sorted array `nums`. The size of `sum` is equal to `n`.

5 : Cumulative Sum Initialization

    sum[0] = nums[0];

Sets the first element of the `sum` array equal to the first element of `nums`.

6 : Cumulative Sum Loop

    for(int i = 1; i < n; i++) sum[i] = sum[i - 1] + nums[i];

Calculates the cumulative sum for each element in `nums`, storing the result in `sum`. The value of `sum[i]` holds the sum of the first `i+1` elements from `nums`.

7 : Triangle Inequality Check Loop

    for(int i = n - 1; i >= 2; i--)

Starts a loop from the last element of the sorted array and moves backward. The loop continues until there are at least three elements to form a triangle.

8 : Triangle Inequality Condition

        if(nums[i] < sum[i - 1])

Checks if the current side `nums[i]` can form a valid triangle by comparing it to the sum of the previous two sides (triangle inequality).

9 : Return Valid Perimeter

            return sum[i];

If the condition is met, return the perimeter of the triangle formed by `nums[i]`, `nums[i-1]`, and `nums[i-2]`, which is the cumulative sum up to `i`.

10 : Return Invalid Case

    return -1;

If no valid perimeter can be formed (i.e., no valid triangle found), return `-1`.

Best Case: O(n log n)

Average Case: O(n log n)

Worst Case: O(n log n)

Description: Sorting the array takes O(n log n), and the scan through the array takes O(n).

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) due to the sorting operation, which requires additional space for the sorted array.

Leetcode 2971: Find Polygon With the Largest Perimeter

Explore →