2971. Find Polygon With the Largest Perimeter


Problem Description

In this problem, we're given an array nums consisting of positive integers which represent potential side lengths of a polygon. A polygon is a closed plane figure with at least three sides, and a crucial property of a valid polygon is that its longest side must be shorter than the sum of its other sides. This problem asks us to determine the largest possible perimeter of a polygon that can be formed using the lengths provided in the nums array. If it's not possible to form a polygon from the given lengths, we must return -1.

The perimeter of a polygon is simply the sum of the lengths of all its sides. The goal is to select three or more lengths from nums that meet the polygon inequality (sum of smaller sides greater than the longest side) and maximize their sum.

Intuition

To solve this problem, we start by sorting the nums array in non-decreasing order. This makes it easier to check the polygon inequality: for any three consecutive lengths in this sorted array, if the sum of the first two is greater than the third, they can form a polygon. Once the array is sorted, we want to check every possible set of three consecutive lengths starting from the longest set and going down.

To achieve this efficiently, we accumulate the sums of nums elements by using the accumulate function from the itertools module, storing prefix sums in array s. E.g., s[k] is the sum from nums[0] to nums[k-1].

We start our check from a polygon with k sides. If the sum of the first k-1 sides (s[k - 1]) is greater than the k-th side (nums[k - 1]), this means there can be a polygon with s[k] as its perimeter. If no such k exists, it means we cannot form a polygon, and thus, we return -1. The answer keeps track of the max perimeter found while satisfying the condition.

Learn more about Greedy, Prefix Sum and Sorting patterns.

Solution Approach

The solution provided applies a greedy approach combined with sort and prefix sum techniques to solve the problem efficiently.

Here is a step-by-step breakdown of the solution implementation.

  1. Sorting: To facilitate the inequality check for forming a polygon, the first step is to sort the array of possible side lengths nums in non-decreasing order. This helps to easily identify the potential largest side for any choice of sides and apply the polygon inequality, which is fundamental for the solution.

    1nums.sort()
  2. Prefix Sums: We utilize the accumulate function from Python's itertools module to compute the prefix sum of the sorted array nums. Prefix sums are helpful to quickly calculate the sum of elements that could form the sides of a potential polygon without repeatedly adding elements in every iteration.

    1s = list(accumulate(nums, initial=0))

    Note that initial=0 is provided so that the accumulation array s starts with a 0, syncing the index of s with the corresponding sum in nums.

  3. Iterating and Checking for a Polygon: The algorithm iterates over the sorted nums array, considering subsets starting from the third element (the smallest possible polygon has three sides) up to the end, checking if the current set can form a polygon.

    1for k in range(3, len(nums) + 1):

    For each subset, the algorithm checks if the sum of the first k-1 side lengths is greater than the k-th side. If this inequality holds, a valid polygon can be formed, and we update the maximum perimeter ans.

    1if s[k - 1] > nums[k - 1]:
    2    ans = max(ans, s[k])
  4. Returning the Largest Perimeter: After the iterations, the variable ans, which is initialized with -1, will contain the largest perimeter found, or -1 if no polygon can be formed.

    1return ans

In this solution, the greedy choice is in selecting the largest potential side combinations starting from the end of the sorted array. The algorithm stops at the largest perimeter found that satisfies the polygon inequality, without the need to check all possible combinations, thus reducing the complexity.

Data structures used include:

  • A list to hold the prefix sums (s).
  • The sorted version of the initial array (nums).

These tools combined allow the solution to efficiently find the largest perimeter of a polygon with sides found in the input array or determine that such a polygon cannot exist.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider the array of sides nums = [2, 1, 2, 4, 3].

  1. Sorting: First, we sort the array to simplify the checking of potential polygons.

    1nums.sort()  # Becomes [1, 2, 2, 3, 4]
  2. Prefix Sums: Next, we use the accumulate function to get the prefix sums.

    1s = list(accumulate(nums, initial=0))  # s becomes [0, 1, 3, 5, 8, 12]
  3. Iterating and Checking for a Polygon: We then iterate over the array, starting from the three smallest sides and move towards the larger ones to check for the possibility of a polygon. The k-th index in nums corresponds to s[k+1] because of the initial=0 in the prefix sum array.

    For k = 3 (first iteration):

    1if s[3 - 1] > nums[3 - 1]:
    2    if 3 > 2:

    This inequality holds, so a polygon can be formed with sides [1, 2, 2] and its perimeter is 3 + 2 = 5.

    For k = 4 (second iteration):

    1if s[4 - 1] > nums[4 - 1]:
    2    if 5 > 3:

    This inequality also holds, so a polygon can be formed with sides [1, 2, 2, 3] and its perimeter is 5 + 3 = 8.

    For k = 5 (third iteration, checking for a triangle):

    1if s[5 - 1] > nums[5 - 1]:
    2    if 8 > 4:

    This inequality holds as well and represents a triangle with sides [2, 3, 4] which has the largest perimeter so far of 8 + 4 = 12.

  4. Returning the Largest Perimeter: The largest perimeter found is 12, so our function would return 12.

In this example, the sorted side lengths allow us to efficiently find the combination [2, 3, 4] with the largest perimeter that satisfies the polygon inequality, without having to check all possible combinations.

Solution Implementation

1from itertools import accumulate
2from typing import List
3
4class Solution:
5    def largest_perimeter(self, nums: List[int]) -> int:
6        # Sort the numbers in non-decreasing order
7        nums.sort()
8      
9        # Generate the cumulative sum of the sorted list, 
10        # with an initial value of 0 to make indices line up
11        cumulative_sum = list(accumulate(nums, initial=0))
12      
13        # Initialize the answer to be 0, where 0 will indicate 
14        # that no triangle can be formed
15        largest_perimeter = 0
16      
17        # Iterate over the sorted numbers from the third element to the end
18        for k in range(3, len(nums) + 1):
19            # Check if the sum of the two smaller sides is greater than the largest side
20            if cumulative_sum[k - 1] > nums[k - 1]:
21                # Update the largest perimeter found so far if the above condition holds
22                # cumulative_sum[k] is the perimeter of a triangle formed by nums[k-3], nums[k-2], nums[k-1]
23                largest_perimeter = max(largest_perimeter, cumulative_sum[k])
24              
25        # Final result, will be 0 if no triangle can be formed
26        return largest_perimeter
27
1// Import the Arrays class for sorting functionality
2import java.util.Arrays;
3
4// Define the Solution class
5class Solution {
6
7    // Method to find the largest perimeter of a triangle that can be formed with given side lengths
8    public long largestPerimeter(int[] nums) {
9      
10        // Sort the array in non-decreasing order.
11        Arrays.sort(nums);
12      
13        // Get the number of elements in the array.
14        int n = nums.length;
15      
16        // Create an array to hold the sum of lengths up to the current index.
17        long[] prefixSums = new long[n + 1];
18      
19        // Compute the prefix sums.
20        for (int i = 1; i <= n; ++i) {
21            prefixSums[i] = prefixSums[i - 1] + nums[i - 1];
22        }
23      
24        // Initialize the variable to store the maximum perimeter found.
25        long maxPerimeter = -1;
26      
27        // Loop over the array to find the maximum perimeter of any triangle that can be formed.
28        for (int k = 3; k <= n; ++k) {
29            // Check if the sum of the two smaller sides is greater than the largest side.
30            if (prefixSums[k - 1] > nums[k - 1]) {
31                // Update the maximum perimeter with the new larger perimeter.
32                maxPerimeter = Math.max(maxPerimeter, prefixSums[k]);
33            }
34        }
35      
36        // Return the maximum perimeter found, or -1 if no triangle can be formed.
37        return maxPerimeter;
38    }
39}
40
1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8    // Function to calculate the largest perimeter of a non-degenerate triangle
9    long long largestPerimeter(vector<int>& nums) {
10        // First, sort the array in non-decreasing order
11        sort(nums.begin(), nums.end());
12      
13        int n = nums.size(); // Size of the input array
14        vector<long long> prefixSum(n + 1); // Vector to store prefix sums
15      
16        // Compute the prefix sums
17        for (int i = 1; i <= n; ++i) {
18            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
19        }
20      
21        long long maxPerimeter = -1; // Initialize the maximum perimeter as -1
22      
23        // Iterate through the array considering each number as the longest side of the triangle
24        for (int k = 3; k <= n; ++k) {
25            // Check if a non-degenerate triangle can be formed
26            // The sum of the any two sides must be greater than the third side
27            if (prefixSum[k - 1] > nums[k - 1]) {
28                // Update the maximum perimeter with the current perimeter if it is larger
29                maxPerimeter = max(maxPerimeter, prefixSum[k]);
30            }
31        }
32      
33        // Return the maximum perimeter found, or -1 if no such triangle exists
34        return maxPerimeter;
35    }
36};
37
1function largestPerimeter(nums: number[]): number {
2    // Sort the input array in non-decreasing order
3    nums.sort((a, b) => a - b);
4
5    // Get the total number of elements in the array
6    const numElements = nums.length;
7  
8    // Initialize a new array to store the cumulative sums
9    // The cumulative sum will be stored such that index 'i' of sumArray
10    // contains the sum of the first 'i' elements of the sorted 'nums' array
11    const sumArray: number[] = Array(numElements + 1).fill(0);
12
13    // Compute the cumulative sums
14    for (let i = 0; i < numElements; ++i) {
15        sumArray[i + 1] = sumArray[i] + nums[i];
16    }
17
18    // Initialize the answer as -1, which will indicate no triangle can be formed
19    let maxPerimeter = -1;
20
21    // Loop through the array to find a valid triangle
22    // Starting from the third element since a triangle needs 3 sides
23    for (let index = 3; index <= numElements; ++index) {
24        // Check if the sum of the smaller two sides is greater than the current side,
25        // which is a necessary and sufficient condition for a non-degenerate triangle.
26        if (sumArray[index - 1] > nums[index - 1]) {
27            // Update the maximum perimeter found so far
28            maxPerimeter = Math.max(maxPerimeter, sumArray[index]);
29        }
30    }
31
32    // Return the maximum perimeter, or -1 if no valid triangle can be formed
33    return maxPerimeter;
34}
35

Time and Space Complexity

The time complexity of the provided code is O(n log n) and the space complexity is O(n).

Time Complexity:

  1. Sorting the list (nums.sort()): Sorting an array of n numbers has a time complexity of O(n log n).

  2. Accumulating the sorted array (list(accumulate(nums, initial=0))): The accumulate function generates a sum of the elements sequentially, hence it has a time complexity of O(n).

  3. The for loop (for k in range(3, len(nums) + 1)): This loop runs (n - 2) times (from 3 to len(nums)), which is O(n).

In the loop, other than the condition check, we have an O(1) assignment for ans variable (ans = max(ans, s[k])).

The dominant term here is from the sorting step, therefore the overall time complexity is O(n log n).

Space Complexity:

  1. The sorted list does not require additional space since sorting is done in-place, hence the space complexity is O(1) for this step.

  2. When creating a list from the accumulate function, we're generating a new list of the same size as nums, hence we have a space complexity of O(n) for this list.

  3. The variables ans and k use constant space, contributing O(1).

Adding these up, the main contribution to space complexity comes from the list generated by the accumulate function, therefore the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄