Find Polygon With the Largest Perimeter - Video Solutions

Problem Overview: You receive an array of integers representing side lengths. The goal is to select some of these sides to form a valid polygon with the largest possible perimeter. A polygon is valid only if the largest side is strictly smaller than the sum of the remaining sides.

The polygon rule generalizes the triangle inequality: maxSide < sum(otherSides). If this condition holds, the chosen sides can form a polygon. The challenge is finding the subset with the maximum perimeter while maintaining this constraint.

Approach 1: Brute Force Approach (O(n²) time, O(1) space)

Start by sorting the array so side lengths are processed in increasing order. For every potential largest side nums[i], compute the sum of all smaller sides and check whether the polygon condition holds. This often requires recomputing sums for each candidate, leading to quadratic time. If nums[i] < sum, a valid polygon exists using the first i + 1 sides, and its perimeter is sum + nums[i]. While simple, repeated summation makes this inefficient for large arrays.

This method is useful for understanding the geometric constraint behind polygon construction. It directly verifies the rule without relying on optimization techniques. However, interview settings usually expect a more efficient solution once the key inequality is recognized.

Approach 2: Sorting + Greedy Prefix Sum (O(n log n) time, O(1) space)

The optimal solution sorts the array and scans it once while maintaining a running prefix sum. Sorting ensures that when you examine a side nums[i], it is the largest among the chosen sides. The prefix sum represents the total length of all smaller sides.

During iteration, check the polygon condition: nums[i] < prefixSum. If true, all sides up to i form a valid polygon with perimeter prefixSum + nums[i]. Update the answer with this value. Continue scanning because adding more sides may increase the perimeter while still satisfying the constraint.

The greedy insight is that larger perimeters come from using as many sides as possible. Because the array is sorted, the inequality only depends on the current largest side and the cumulative sum before it. Maintaining a running sum eliminates repeated computations and keeps the algorithm linear after sorting.

This approach relies heavily on sorting to order candidate sides and a running sum similar to a prefix sum. The decision step follows a classic greedy strategy: extend the polygon whenever the inequality allows it.

Recommended for interviews: The sorting + greedy prefix sum solution is the expected approach. It demonstrates recognition of the polygon inequality and efficient use of sorted order. Showing the brute force idea first can help explain the constraint, but implementing the optimized version proves you can reduce repeated work and reach the optimal O(n log n) complexity.