Find Polygon With the Largest Perimeter - Practice Coding Problems

Find Polygon With the Largest Perimeter - Problem

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

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.

Input & Output

Example 1 — Basic Valid Polygon

$ Input: nums = [5,5,5,2,10,15]

› Output: 42

💡 Note: After sorting: [2,5,5,5,10,15]. All elements form a valid polygon because 15 < 2+5+5+5+10 = 27. Total perimeter = 42.

Example 2 — No Valid Polygon

$ Input: nums = [1,12,1,2,5,50,3]

› Output: -1

💡 Note: After sorting: [1,1,2,3,5,12,50]. No subset can form a valid polygon because any combination with 50 fails (50 ≥ sum of others), and without 50, 12 ≥ sum of remaining elements.

Example 3 — Minimum Size Triangle

$ Input: nums = [3,3,5]

› Output: 11

💡 Note: After sorting: [3,3,5]. Forms valid triangle since 5 < 3+3 = 6. Perimeter = 3+3+5 = 11.

Constraints

3 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of positive integers representing potential side lengths

Sort & Check

Sort elements and find largest valid polygon combination

Return Perimeter

Sum of all sides in the largest valid polygon

Key Takeaway

🎯 Key Insight: Sort the array and greedily check from largest combinations - the first valid polygon found will have the maximum perimeter

Asked in

a Amazon 25 G Google 18 f Facebook 12 M Microsoft 8

The key insight is that for a valid polygon, the longest side must be smaller than the sum of all other sides. The optimal approach sorts the array and uses prefix sums to efficiently check polygon validity in O(1) time per combination. Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subsets	O(2ⁿ × n log n)	O(n)	Generate all possible subsets of 3+ elements and check polygon validity
Sort and Check Greedily	O(n²)	O(1)	Sort array, then greedily try largest possible combinations
Optimal: Sort + Prefix Sum	O(n²)	O(n)	Sort array, use prefix sums, and check from largest to smallest combinations

Brute Force - Try All Subsets — Algorithm Steps

Generate all subsets of size ≥ 3
For each subset, sort elements
Check if max < sum of others
Track maximum valid perimeter

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all combinations of 3+ elements

Check Validity

For each subset, verify polygon condition

Track Maximum

Keep the largest valid perimeter found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

long long solution(int* nums, int n) {
    long long maxPerimeter = -1;
    
    // Try all subsets of size 3 or more
    for (int mask = 0; mask < (1 << n); mask++) {
        int subset[20];
        int subsetSize = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subset[subsetSize++] = nums[i];
            }
        }
        
        if (subsetSize >= 3) {
            qsort(subset, subsetSize, sizeof(int), compare);
            long long largest = subset[subsetSize - 1];
            long long sumOthers = 0;
            for (int i = 0; i < subsetSize - 1; i++) {
                sumOthers += subset[i];
            }
            
            if (largest < sumOthers) {
                long long perimeter = largest + sumOthers;
                if (perimeter > maxPerimeter) {
                    maxPerimeter = perimeter;
                }
            }
        }
    }
    
    return maxPerimeter;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[20];
    int n = 0;
    char *ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char *token = strtok(ptr, ",]");
        while (token && n < 20) {
            nums[n++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    long long result = solution(nums, n);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n log n)

2^n subsets, each requiring O(n log n) sorting

⚡ Linearithmic

Space Complexity

O(n)

Space for storing current subset and sorting

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Subsets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler