Find Polygon With the Largest Perimeter

Find Polygon With the Largest Perimeter

What is this problem about?

The Find Polygon With the Largest Perimeter interview question is a geometry-based array problem. A polygon with $k$ sides ($k \geq 3$) can only be formed if the length of its longest side is strictly less than the sum of the lengths of the other $k-1$ sides. You are given an array of side lengths, and you need to find the maximum possible perimeter of any polygon that can be constructed using a subset of these lengths.

Why is this asked in interviews?

Companies like Microsoft and Airtel ask this to evaluate your understanding of Greedy interview patterns and sorting. It tests if you can identify that to maximize the perimeter, you should try to include as many large sides as possible, provided they satisfy the polygon inequality theorem. It’s a test of combining Math interview patterns with efficient array processing.

Algorithmic pattern used

This problem follows the Greedy and Prefix Sum patterns.

1. Sort: Sort the array of side lengths in ascending order.
2. Prefix Sums: Calculate the prefix sums of the sorted array. The sum of the first $i$ elements represents the "sum of all other sides" for the side at index $i$.
3. Iterate Backwards: Start from the largest side (the end of the sorted array).
4. Validation: For each side nums[i], check if nums[i] < prefixSum[i].
   • If true, you can form a polygon using all elements from $0$ to $i$. The perimeter is prefixSum[i] + nums[i]. Since you started from the largest possible i, this is your maximum perimeter.
   • If false, you cannot use nums[i] as the longest side. Move to $i-1$.

Example explanation

Array: [1, 12, 1, 2, 5, 50]

1. Sorted: [1, 1, 2, 5, 12, 50]
2. Prefix sums: [0, 1, 2, 4, 9, 21] (where prefixSum[i] is sum of elements 0 to i-1).
3. Check 50: $50 < 21$ is False.
4. Check 12: $12 < 9$ is False.
5. Check 5: $5 < 4$ is False.
6. Check 2: $2 < 2$ is False. Wait, let's re-calculate: [1, 1, 2]. $2 < 1+1$ is False. Example 2: [5, 5, 5]

• Sorted: [5, 5, 5]. Prefix Sum for last 5: $5+5=10$. $5 < 10$ is True. Perimeter = 15.

Common mistakes candidates make

• Not Sorting: Trying to find subsets without sorting, which makes the greedy choice impossible to identify efficiently.
• Strict Inequality: Forgetting that the longest side must be strictly less than the sum of others.
• Subset Selection: Thinking you can pick any subset, when in reality, if a side $S$ is valid with sum $X$, it will always be valid (and larger) if you include all available smaller sides.

Interview preparation tip

Whenever a problem involves a "sum of others" constraint (like the triangle inequality), Sorting is almost always the prerequisite. It allows you to check the most constrained case (the largest element) against the largest possible pool of support (all smaller elements).