Find Polygon with the Largest Perimeter LeetCode

Optimal resource allocation is crucial in any problem.

Imagine you are a civil engineer tasked with planning the construction of a fence around a rectangular garden. You have a list of available fence panels, each represented by its length in meters.

For example, suppose the available fence panels are as follows:

In this scenario:

The fence must be constructed using the available fence panels.
Each fence panel can only be used once.

We aim to determine the largest possible perimeterThe perimeter of a shape is the total distance around the outer edges of that shape. It is the sum of the lengths of all the sides or edges that form the boundary of a two-dimensional figure. of the fence that can be constructed using these panels.

Problem statement

Given a list of integers nums , find the polygon with the largest perimeter that can be formed using the sides given.

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.

Constraint

A polygon is a closed shape with at least three sides, and a rule for a valid polygon is that the length of the longest side must be smaller than the sum of the other sides.

Examples

Algorithm

To solve the problem of finding the largest perimeter of a polygon that can be formed from a given array of side lengths, our approach leverages sorting and iterative checking. By sorting the array in ascending order, we systematically evaluate each side length to determine if it can form a valid polygon based on the triangle inequality condition. This method ensures efficiency by prioritizing longer sides towards the end of the array, simplifying the process of checking if the longest side is smaller than the sum of the others.

Now, let's look at the algorithm for this approach:

Begin by sorting the array, nums in the ascending order.
Initialize two variables: total set to 0 and result set to -1.
Iterate through each element num in the sorted array nums.
Check if the current element num satisfies the condition where it is less than the sum of the previously encountered elements. If true, this indicates a valid combination of sides.
If num forms a valid side, update result to the sum of num and total.
Update total by adding the current element num.
Upon completing the iteration through all elements, return the largest possible perimeter stored in result.

Now, let's have a look at the illustration below for better understanding.

def largest_perimeter(nums):
  nums.sort()
  total = 0
  result = -1
  for num in nums:
    if num < total:
        result = num + total
    total += num
  return result
def main():
  test_cases = [
    [5, 5, 5],                 
    [1, 12, 1, 2, 5, 50, 3],   
    [5, 5, 50],               
    [3, 6, 2, 3],             
    [2, 2, 1, 5, 5, 3]
  ]
    
  for i, nums in enumerate(test_cases):
    result = largest_perimeter(nums)
    print(f"Example {i + 1}: Perimeter for {nums} is {result}")
if __name__ == "__main__":
    main()

Time complexity

The time complexity of the provided code is dominated by the sorting operation, which has a time complexity of $O(n log n)$ . The subsequent iteration through the sorted list of length $n$ has a linear time complexity of $O(n)$ . Therefore, the overall time complexity of the code is $O(n log n)$ due to the sorting step.

Space complexity

It takes $O(N)$ space as 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.