We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Polygon With the Largest Perimeter

Number: 3262

Difficulty: Medium

Paid? No

Companies: Microsoft, Bloomberg, Airtel

Problem Description

Given an array of positive integers representing potential side lengths, determine the largest perimeter of any polygon that can be formed using these sides. A polygon is valid if it has at least 3 sides and the longest side is strictly less than the sum of the remaining sides. If no valid polygon exists, return -1.

Key Insights

  • A polygon must have at least three sides.
  • The polygon inequality: the longest side must be less than the sum of the other sides.
  • Sorting the array allows us to easily access and check the potential longest side.
  • A greedy approach can be used by trying to use as many sides as possible to maximize the perimeter and removing the largest value if the condition fails.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array.
Space Complexity: O(1) extra space if sorting is done in-place.

Solution

Sort the array in non-decreasing order. Check if the current set of numbers (using all the numbers) forms a valid polygon by verifying that the sum of the lengths of the sides, except for the largest one, is greater than the largest side. If the condition is met, return the sum as the perimeter. If not, remove the largest side (as it is preventing the formation of a polygon) and check again. Continue until a valid polygon is found or fewer than 3 sides remain.

Code Solutions

# Python solution with line-by-line comments
def largestPerimeter(nums):
    # Sort the side lengths in non-decreasing order
    nums.sort()
    # Continue checking while there are at least 3 sides
    while len(nums) >= 3:
        # The last three elements are the biggest; check the polygon condition
        if nums[-3] + nums[-2] > nums[-1]:
            # Return the sum of all sides if the condition is satisfied
            return sum(nums)
        # Remove the largest side and try forming a polygon with the remaining sides
        nums.pop()
    # If no valid polygon can be formed, return -1
    return -1

# Example usage:
print(largestPerimeter([5,5,50]))  # Expected output: -1
← Back to All Questions