What is the time complexity of Find Polygon With the Largest Perimeter?

The optimal solution has a time complexity of O(n log n).

What data structures are used to solve Find Polygon With the Largest Perimeter?

This problem uses Array, Greedy, Sorting, Prefix Sum. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Find Polygon With the Largest Perimeter?

Insight 1: Sorting the input array allows us to efficiently consider the longest side candidates in descending order, and easily calculate the sum of the smaller sides. Insight 2: Using a prefix sum approach (although implicitly) allows to quickly determine if the sum of the shorter sides exceeds the length of the current longest side candidate.

Which companies ask LeetCode 2971. Find Polygon With the Largest Perimeter in interviews?

This problem is frequently asked at Airtel.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Find Polygon With the Largest Perimeter - LeetCode 2971 Solution

Find Polygon With the Largest Perimeter - Complete Solution Guide

Find Polygon With the Largest Perimeter is LeetCode problem 2971, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given an array of positive integers nums of length n . A polygon is a closed plane figure that has at least 3 sides. The longest side of a polygon is smaller than the sum of its other sides. Conversely, if you have k ( k >= 3 ) positive real numbers a 1 , a 2 , a 3 , ..., a k where a 1 <= a 2 <= a 3 <= ... <= a k and a 1 + a 2 + a 3 + ... + a k-1 > a k , then there always exists a polygon with k sides whose lengths are a 1 , a 2 , a 3 , ..., a k . The perimeter of a polygon is the sum of

Detailed Explanation

The problem asks us to find the largest possible perimeter of a polygon that can be formed using the given array of positive integers `nums` as side lengths. A polygon must have at least 3 sides. The key constraint is that the length of the longest side must be strictly less than the sum of the lengths of the other sides. If no such polygon can be formed, we return -1.

Solution Approach

The solution first sorts the input array `nums` in ascending order. Then, it calculates the total sum of all the numbers in the array. The solution iterates through the sorted array from right to left (largest to smallest number) considering each number as the longest side of a potential polygon. For each longest side, the sum of the remaining numbers is compared to the longest side. If the sum of the remaining numbers is greater than the longest side, a valid polygon can be formed using these numbers, and the total sum is returned as the largest possible perimeter. If no such polygon can be formed after checking all possible longest sides, -1 is returned.

Step-by-Step Algorithm

Step 1: Sort the input array `nums` in ascending order.
Step 2: Calculate the total sum of all elements in `nums`.
Step 3: Iterate through the array `nums` from right to left (from the largest element to the third element) using a loop with index `i`.
Step 4: In each iteration, consider `nums[i]` as the longest side of the polygon.
Step 5: Calculate the sum of the other sides by subtracting `nums[i]` from the total sum.
Step 6: Check if the sum of the other sides is greater than `nums[i]`. If it is, return the total sum as the largest possible perimeter.
Step 7: If the sum of the other sides is not greater than `nums[i]`, subtract `nums[i]` from the total sum and continue the iteration.
Step 8: If the loop completes without finding a valid polygon, return -1.

Key Insights

Insight 1: Sorting the input array allows us to efficiently consider the longest side candidates in descending order, and easily calculate the sum of the smaller sides.
Insight 2: Using a prefix sum approach (although implicitly) allows to quickly determine if the sum of the shorter sides exceeds the length of the current longest side candidate.
Insight 3: Iterating from the largest number to the smallest allows us to stop as soon as we find a solution because the numbers are sorted. Smaller numbers cannot form a greater perimeter.

Complexity Analysis

Time Complexity: O(n log n)

Space Complexity: O(1)

Topics

This problem involves: Array, Greedy, Sorting, Prefix Sum.

Companies

Asked at: Airtel.

Find Polygon With the Largest Perimeter | LeetCode 2971

Medium

Array Greedy Sorting Prefix Sum

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

Solution Code

Available in:

import java.util.Arrays;

class Solution {
    public long largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        
        long total_sum = 0;
        for (int num : nums) {
            total_sum += num;
        }
        
        int n = nums.length;
        
        for (int i = n - 1; i > 1; i--) {
            // The longest side candidate is nums[i]
            // The sum of other sides is total_sum - nums[i]
            if (total_sum - nums[i] > nums[i]) {
                return total_sum;
            }
            
            // If the condition fails, we can't use nums[i].
            // We remove it from our consideration and from the sum.
            total_sum -= nums[i];
            
        }
        
        return -1;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2971: Find Polygon With the Largest Perimeter - Detailed explanation and solution approaches.

Topics

Array Greedy Sorting Prefix Sum

Companies

Airtel

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:2971

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Sort the input array `nums` in ascending order.
2
Step 2: Calculate the total sum of all elements in `nums`.
3
Step 3: Iterate through the array `nums` from right to left (from the largest element to the third element) using a loop with index `i`.
4
Step 4: In each iteration, consider `nums[i]` as the longest side of the polygon.
5
Step 5: Calculate the sum of the other sides by subtracting `nums[i]` from the total sum.
6
Step 6: Check if the sum of the other sides is greater than `nums[i]`. If it is, return the total sum as the largest possible perimeter.
7
Step 7: If the sum of the other sides is not greater than `nums[i]`, subtract `nums[i]` from the total sum and continue the iteration.
8
Step 8: If the loop completes without finding a valid polygon, return -1.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n log n)

✨ Log-linear - Great for sorting algorithms!

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

Sorting uses O(n log n). The rest of the code involves a single loop through the array, and some arithmetic operations, which take O(n) time in total. Since O(n log n) dominates O(n), the total time complexity is O(n log n). The algorithm uses a fixed number of variables, so the space complexity is O(1).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Generate all possible subsets of `nums` with at least 3 elements, and for each subset, check if it forms a valid polygon and calculate its perimeter. Keep track of the largest perimeter found so far.

Time: O(2^n * n), because we need to generate all possible subsets (2^n) and for each subset of size k we perform O(k) calculations.Space: O(n), for storing the subset.

Trade-offs: This approach is very inefficient and would result in a Time Limit Exceeded (TLE) error for larger input arrays. Use it if n is very small, but the main approach is much more performant.

✨

Key Insights

1Insight 1: Sorting the input array allows us to efficiently consider the longest side candidates in descending order, and easily calculate the sum of the smaller sides.
2Insight 2: Using a prefix sum approach (although implicitly) allows to quickly determine if the sum of the shorter sides exceeds the length of the current longest side candidate.
3Insight 3: Iterating from the largest number to the smallest allows us to stop as soon as we find a solution because the numbers are sorted. Smaller numbers cannot form a greater perimeter.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Greedy Algorithm

Making the best choice at each step without looking ahead.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: The input array `nums` has fewer than 3 elements. The problem statement specifies that 3 <= n <= 10^5, so this case is not a possibility according to the problem description, therefore is not explicitly checked.
Edge case 2: No polygon can be formed. In this case, the algorithm correctly returns -1 after iterating through the entire array without finding a valid polygon.
Edge case 3: Array is sorted in descending order. The algorithm will still work correctly as the sorting step puts the array in the correct order.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to sort the array before iterating through it. Sorting is crucial to ensure that we consider the longest sides in descending order and efficiently calculate the sum of the shorter sides.

✗Common mistake 2: Not handling the case where no polygon can be formed and returning -1. It's important to return -1 in this scenario, as stated in the problem description.

✗Common mistake 3: Incorrectly calculating the sum of the other sides. The other sides should be calculated by substracting current longest side from total sum.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: This algorithm can be used in geometry or CAD (Computer-Aided Design) software to determine if a set of line segments can form a valid polygon and to calculate its perimeter.

🏦Real-world scenario 2: Resource allocation: Imagine you have different resources with associated costs and want to find the maximum resource allocation set which obeys certain constraints (like the sum of smaller resources outweighing the largest). This is an analogous application of the problem.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 31, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

What are common greedy problem patterns?

Activity selection (sort by end time), interval scheduling (sort by start/end), Huffman coding (always combine smallest), fractional knapsack (sort by value/weight ratio), and minimum spanning tree. Look for problems where local decisions don't affect future options.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Find Polygon With the Largest Perimeter"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether greedy techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?