Skip to content

2971. Find Polygon With the Largest Perimeter 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  long long largestPerimeter(vector<int>& nums) {
    long prefix = accumulate(nums.begin(), nums.end(), 0L);

    ranges::sort(nums);

    for (int i = nums.size() - 1; i >= 2; --i) {
      prefix -= nums[i];
      // Let nums[i] be the longest side. Check if the sum of all the edges with
      // length no longer than nums[i] > nums[i].
      if (prefix > nums[i])
        return prefix + nums[i];
    }

    return -1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public long largestPerimeter(int[] nums) {
    long prefix = Arrays.stream(nums).asLongStream().sum();

    Arrays.sort(nums);

    for (int i = nums.length - 1; i >= 2; --i) {
      prefix -= nums[i];
      // Let nums[i] be the longest side. Check if the sum of all the edges with
      // length no longer than nums[i] > nums[i].
      if (prefix > nums[i])
        return prefix + nums[i];
    }

    return -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def largestPerimeter(self, nums: list[int]) -> int:
    prefix = sum(nums)

    for num in sorted(nums, reverse=True):
      prefix -= num
      # Let `num` be the longest side. Check if the sum of all the edges with
      # length no longer than `num` > `num``.
      if prefix > num:
        return prefix + num

    return -1