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.

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

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.