LeetCode Entry

2971. Find Polygon With the Largest Perimeter

15.02.2024 medium 2024 kotlin rust

The largest subset sum(a[..i]) > a[i + 1] where a is a subset of array.

2971. Find Polygon With the Largest Perimeter medium blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/506

Problem TLDR

The largest subset sum(a[..i]) > a[i + 1] where a is a subset of array.

Intuition

First, understand the problem: [1,12,1,2,5,50,3] doesn’t have a polygon, but [1,12,1,2,5,23,3] does. After this, the solution is trivial: take numbers in increasing order, compare with sum and check.

Approach

Let’s try to use the languages.

  • Kotlin: sorted, fold
  • Rust: sort_unstable, iter, fold

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(1)\), sorted takes O(n) but can be avoided

Code


  fun largestPerimeter(nums: IntArray) = nums
    .sorted()
    .fold(0L to -1L) { (s, r), x ->
      s + x to if (s > x) s + x else r
    }.second



  pub fn largest_perimeter(mut nums: Vec<i32>) -> i64 {
    nums.sort_unstable();
    nums.iter().fold((0, -1), |(s, r), &x|
      (s + x as i64, if s > x as i64 { s + x as i64 } else { r })
    ).1
  }