February-Leetcode-POTD- 15: 2971. Find Polygon With the Largest Perimeter

QUESTION -> Find Polygon With the Largest Perimeter

Problem Statement:

We have an array of positive integers nums of length n. And we have to return the largest possible perimeter of a polygon whose sides can be formed from nums , based on some conditions or -1 if it is not possible to create a polygon.

Condition

1 ) A polygon is a closed plane figure that has at least 3 sides.

2 ) The longest side of a polygon is smaller than the sum of its other sides.

Ex -> if we have (k ≥3 ) positive real numbers (a1,a2,a3 …,ak) where ((a1 ≤ a2 ≤ a3 ≤ … ≤ ak-1) > ak ), then there is always a polygon with k sides.

The perimeter of a polygon is the sum of lengths of its sides.

Approach :

1. Sort the array: Start by sorting the array of numbers in ascending order.
2. Initialize variables: Set up variables to track the sum (sum) (sum = nums[0] + nums[1] ) and the largest perimeter found so far (perimeter).
3. Iterate through the sorted array starting from idx 2 as min length will be 3 : Loop through each number in the sorted array.
4. Check polygon condition: For each number, check if it’s smaller than the sum of all previous numbers encountered.
5. Update largest perimeter: If the condition is met, update perimeter with the sum of the current number and the running sum. Finally, return the largest perimeter found (perimeter).

Complexity

• Time complexity: O(n logn) .
• Space complexity: O(n)

CODE :

Note : Hi reader’s , I’m just trying to share my approaches. Due to time constraint i’m not be able to briefly explain my approaches in some posts , so please bear me for this. If you have any suggestions please let me know.

HOPE YOU LIKE MY APPROACH!!!

Thank you For Reading!!!

Shubham Saha