Find Polygon With the Largest Perimeter

Medium

Asked by:

16 views

Topics:

ArraysGreedy Algorithms

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 a₁, a₂, a₃, ..., a_k where a₁ <= a₂ <= a₃ <= ... <= a_k and a₁ + a₂ + a₃ + ... + a_k-1 > a_k, then there always exists a polygon with k sides whose lengths are a₁, a₂, a₃, ..., a_k.

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 <= 10⁵
1 <= nums[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of values for the integers in the `nums` array? Are there any constraints on the maximum size of an integer?
Can the input array `nums` be empty or null? If so, what should I return?
If multiple subsets of line segments can form a polygon with the same maximum perimeter, is any one of them acceptable, or is there a specific criterion for selecting the 'largest' in that case?
Are all the side lengths positive integers, as stated in the description? Can I assume no negative or zero values?
What is the minimum number of line segments required to form a valid polygon? (e.g., Must it be at least 3?)

Brute Force Solution

Approach

The goal is to find the largest polygon you can make from a set of line segments. A brute force approach means trying every possible combination of segments to see which one makes the biggest polygon.

Here's how the algorithm would work step-by-step:

First, consider all possible groups of three segments. Check if these segments can form a triangle, using the rule that the sum of any two sides must be greater than the third side.
Calculate the perimeter of each valid triangle (sum of the sides).
Next, consider all possible groups of four segments. Check if these segments can form a quadrilateral (a four-sided shape). This is trickier than a triangle, but you need to make sure it's actually possible to build the shape.
Calculate the perimeter of each valid quadrilateral.
Continue this process for polygons with five sides, six sides, and so on, up to the number of line segments you have. For each number of sides, check all possible combinations of segments.
Each time you find a valid polygon, calculate its perimeter.
Finally, compare the perimeters of all the valid polygons you found. The largest one is the answer.

Code Implementation

from itertools import combinations

def find_largest_polygon_perimeter_brute_force(side_lengths):
    number_of_sides = len(side_lengths)
    largest_perimeter = 0

    for polygon_size in range(3, number_of_sides + 1):

        # Iterate over all possible combinations of sides
        for combination in combinations(side_lengths, polygon_size):
            if can_form_polygon(combination):
                perimeter = sum(combination)

                # Update the largest perimeter if necessary
                largest_perimeter = max(largest_perimeter, perimeter)

    return largest_perimeter

def can_form_polygon(sides):

    # Check that the sum of all sides but the longest is greater than the longest side
    longest_side = max(sides)
    sum_of_other_sides = sum(sides) - longest_side

    if sum_of_other_sides > longest_side:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(2^n * n) – The algorithm considers all possible combinations of line segments to form polygons. This involves iterating through all subsets of the input array of size n. The number of subsets is 2^n. For each subset, the algorithm needs to check if the segments can form a valid polygon, which can take O(n) time, since it has at most n segments to check. Therefore, the overall time complexity is O(2^n * n).

Space Complexity

O(1) – The provided algorithm, based on the plain English explanation, primarily iterates through combinations of line segments and calculates perimeters. It doesn't appear to use auxiliary data structures that scale with the input size N (the number of line segments), such as temporary arrays or hashmaps to store intermediate results during polygon validation or perimeter comparison. It seems to rely on comparing perimeter values directly. Therefore, the extra space used remains constant regardless of N.

Optimal Solution

Approach

To find the polygon with the largest perimeter, we need to efficiently pick the longest possible sides. Sorting the sides allows us to quickly consider the longest ones first and check if they can form a valid polygon.

Here's how the algorithm would work step-by-step:

First, arrange all the sides from longest to shortest.
Start with the longest three sides.
Check if these three sides can actually form a polygon. This means the sum of the two shorter sides must be greater than the longest side.
If they can form a polygon, you've found your answer. The perimeter is simply the sum of these sides.
If they can't form a polygon, discard the shortest side and try the next longest side from the sorted list in its place.
Repeat the process of checking if they can form a polygon. Keep doing this until you find a valid polygon or run out of sides.
If you run out of sides without finding a valid polygon, it means no polygon can be formed from the given sides, so the answer is zero.

Code Implementation

def find_polygon_with_largest_perimeter(sides):
    sides.sort(reverse=True)

    number_of_sides = len(sides)

    for i in range(number_of_sides - 2):
        # Iterate through the sides, checking polygon validity
        longest_side = sides[i]
        second_longest_side = sides[i+1]
        third_longest_side = sides[i+2]

        # Check if the three sides can form a valid polygon
        if second_longest_side + third_longest_side > longest_side:
            polygon_perimeter = longest_side + second_longest_side + third_longest_side
            return polygon_perimeter

    return 0

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the input array of size n, which takes O(n log n) time. After sorting, the algorithm iterates through the array to find a valid polygon. In the worst case, this iteration might examine a significant portion of the sorted array. However, the sorting step dictates the overall time complexity. Therefore, the time complexity is O(n log n).

Space Complexity

O(1) – The algorithm sorts the input array of size N in place. While sorting algorithms can have varying space complexities, the problem description doesn't dictate a specific sorting algorithm. Let's assume a sorting algorithm with O(1) auxiliary space, like heapsort, is used. The subsequent steps involve only a few integer variables for indexing and sum calculation. Therefore, the space used beyond the input array is constant and independent of N.

Edge Cases

Case	How to Handle
Empty input array	Return -1 immediately as no polygon can be formed with no sides.
Input array with fewer than 3 elements	Return -1 because a polygon needs at least 3 sides.
Input array with very large numbers leading to potential integer overflow during perimeter calculation	Use a data type that can accommodate large numbers (e.g., long in Java or C++) or check for overflow before returning the result.
Input array containing all identical values	The algorithm should still correctly calculate the perimeter, ensuring at least three identical values are present.
Input array where no subset can form a valid polygon (e.g., [1, 2, 100])	Return -1 as no combination of sides satisfies the polygon inequality theorem.
Input array with a very large number of elements to assess time complexity	Ensure the chosen algorithm has a time complexity of O(n log n) due to sorting (or better) to avoid exceeding time limits, if input sizes reach millions.
Input array contains only small values	Algorithm should accurately calculate the largest perimeter, even with smaller integers.
Array sorted in descending order	Sorting algorithm should correctly handle a reverse-sorted array without causing performance issues.

Empty input array

How to Handle:

Return -1 immediately as no polygon can be formed with no sides.

Input array with fewer than 3 elements

How to Handle:

Return -1 because a polygon needs at least 3 sides.

Input array with very large numbers leading to potential integer overflow during perimeter calculation

How to Handle:

Use a data type that can accommodate large numbers (e.g., long in Java or C++) or check for overflow before returning the result.

Input array containing all identical values

How to Handle:

The algorithm should still correctly calculate the perimeter, ensuring at least three identical values are present.

Input array where no subset can form a valid polygon (e.g., [1, 2, 100])

How to Handle:

Return -1 as no combination of sides satisfies the polygon inequality theorem.

Input array with a very large number of elements to assess time complexity

How to Handle:

Ensure the chosen algorithm has a time complexity of O(n log n) due to sorting (or better) to avoid exceeding time limits, if input sizes reach millions.

Input array contains only small values

How to Handle:

Algorithm should accurately calculate the largest perimeter, even with smaller integers.

Array sorted in descending order

How to Handle:

Sorting algorithm should correctly handle a reverse-sorted array without causing performance issues.