Skip to main content
Back to problems
#2971
Medium Algorithms

Find polygon with the largest perimeter

Array Greedy Sorting Prefix Sum
65.5% acceptance
Feb 25, 2026
836
71
You are given an array of positive integers nums of length n. A polygon is a closed plane figure with at least 3 sides. The longest side of a polygon is smaller than the sum of its other sides. Return the largest possible perimeter of a polygon whose sides can be formed from nums, or -1 if it is not possible.

Solution

Rust
Time O(n log n)
Space O(1)
LeetCode
solution.rs 
impl Solution {
  pub fn largest_perimeter(nums: Vec<i32>) -> i64 {
    let mut sorted = nums.clone();
    sorted.sort_unstable();
    let n = sorted.len();
    let mut prefix_sum = 0i64;
    let mut ans = -1i64;
    for i in 0..n {
      if prefix_sum > sorted[i] as i64 {
        // polygon valid with all elements 0..i
        ans = prefix_sum + sorted[i] as i64;
      }
      prefix_sum += sorted[i] as i64;
    }
    ans
  }
}