Find Polygon With the Largest Perimeter

medium prefix sum greedy sorting

Problem

Given positive integers nums, a polygon needs at least 3 sides and its longest side must be strictly smaller than the sum of the others. After sorting, if sides a₁ ≤ a₂ ≤ … ≤ aₖ satisfy a₁ + … + aₖ₋₁ > aₖ, a valid polygon exists with perimeter equal to their sum. Return the largest possible perimeter, or -1 if no polygon can be formed.

Inputnums = [1,12,1,2,5,50,3]

Output12

Sorted: [1,1,2,3,5,12,50]. Sides 1+1+2+3 = 7 > 5, so 1,1,2,3,5 form a polygon with perimeter 12. Neither 12 nor 50 can be a longest side (the smaller sides never out-sum them).

nums (comma-separated positive integers)

def largestPerimeter(nums):
    nums.sort()                       # sides ascending
    n = len(nums)
    prefix = [0] * (n + 1)            # prefix[i] = sum of nums[0..i-1]
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    best = -1
    for i in range(2, n):            # nums[i] is the candidate longest side
        if prefix[i] > nums[i]:      # shorter sides out-sum it?
            best = prefix[i] + nums[i]   # perimeter = prefix[i + 1]
    return best

function largestPerimeter(nums) {
  nums.sort((a, b) => a - b);          // sides ascending
  const n = nums.length;
  const prefix = new Array(n + 1).fill(0); // prefix[i] = sum of nums[0..i-1]
  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }
  let best = -1;
  for (let i = 2; i < n; i++) {        // nums[i] is the candidate longest side
    if (prefix[i] > nums[i]) {         // shorter sides out-sum it?
      best = prefix[i] + nums[i];      // perimeter = prefix[i + 1]
    }
  }
  return best;
}

long largestPerimeter(int[] nums) {
    Arrays.sort(nums);                  // sides ascending
    int n = nums.length;
    long[] prefix = new long[n + 1];    // prefix[i] = sum of nums[0..i-1]
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    long best = -1;
    for (int i = 2; i < n; i++) {        // nums[i] is the candidate longest side
        if (prefix[i] > nums[i]) {       // shorter sides out-sum it?
            best = prefix[i] + nums[i];  // perimeter = prefix[i + 1]
        }
    }
    return best;
}

long long largestPerimeter(vector<int>& nums) {
    sort(nums.begin(), nums.end());     // sides ascending
    int n = nums.size();
    vector<long long> prefix(n + 1, 0);  // prefix[i] = sum of nums[0..i-1]
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    long long best = -1;
    for (int i = 2; i < n; i++) {        // nums[i] is the candidate longest side
        if (prefix[i] > nums[i]) {       // shorter sides out-sum it?
            best = prefix[i] + nums[i];  // perimeter = prefix[i + 1]
        }
    }
    return best;
}

Explanation

The polygon rule says the longest side must be strictly smaller than the sum of all the other sides. So the whole problem reduces to: pick a set of sides, look at the biggest one, and check whether the rest out-sum it.

First sort the array ascending. Now if we decide that nums[i] is the longest side, the cheapest way to satisfy the rule is to include every side before it — adding more smaller sides only grows the competing sum and never makes the biggest side larger. That sum of everything before index i is exactly a prefix sum.

We build prefix so that prefix[i] holds the sum of nums[0..i-1]. Then for each candidate longest side nums[i] (we need at least 3 sides, so i ≥ 2), the polygon is valid exactly when prefix[i] > nums[i], and its perimeter is prefix[i] + nums[i], which equals prefix[i + 1].

Because the array is sorted, a larger index always means a larger perimeter, so we simply keep the last valid candidate — the rightmost i that passes the test gives the answer. If no index passes, no polygon exists and we return -1.

Example: [1,12,1,2,5,50,3] sorts to [1,1,2,3,5,12,50]. At the side 5 the shorter sides sum to 1+1+2+3 = 7 > 5, giving perimeter 12. At 12 the prefix is 12 (not strictly greater), and at 50 the prefix 24 is far too small — so 12 wins.

Time: O(n log n) Space: O(n)