In this tutorial, we are going to Find Polygon with the Largest Perimeter in Java. Any closed, three-sided figure on a plane is called a polygon. A polygon's longest side is not equal to the sum of its other side lengths.

The total length of all of a polygon's sides determines its perimeter.

Example 1:

Input: nums = [15,15,15]

Output: 45

Explanation: The only possible polygon that can be made from nums has 3 sides: 15, 15, and 15.

The perimeter is 15 + 15 + 15 = 45.

Example 2:

Input: nums = [5,5,50]

Output: -1

Explanation: Nums cannot be used to create a polygon since a polygon has three sides at minimum and 50 > 5 + 5.

Approach 1: Making use of prefix sum

The approach uses prefix sums and array sorting. It establishes whether polygon creation is feasible. computes prefix sums for each member in the array iteratively in order to get the largest perimeter.

Step 1: First, confirm that the array nums's length is less than three. When this happens, the method cannot generate a polygon and returns -1.

Step 2: Ensure that the integers in the array do not decrease, sort them. This is significant for the process since it facilitates determining the longest side of the potential polygon.

Step 3: Set the prefix sum of the components in numerical form, create and initialize a prefSum array. This array will make calculating the side sum of the polygon quick and easy.

Step 4: Add up the sums as we go through the sorted array of numbers, we may determine the prefix sum.

Step 5: Use prefSum[i-1] to determine if the current element is less than the sum of the items that came before it for each element. After then, the array nums are iterated over, beginning with the third entry (index 2). In the event that this is the case, the maximum value of the peri variable and the total side lengths at this moment are adjusted.

Step 6: Find the value of perimeter using the array nums, which denotes the maximum polygonal perimeter, that is finally returned.

Filename: LargestPerimeter.java

import java.util.Arrays;

public class LargestPerimeter {

    public long largestPerimeter(int[] num) {

        Arrays.sort(num);

        long largestPerimeter = -1;

            for (int i = num.length - 1; i >= 2; i--) {

            if (num[i - 2] + num[i - 1] > num[i]) {

                largestPerimeter = (long) num[i - 2] + num[i - 1] + num[i];

                break;

            }

        }

        return largestPerimeter;

    }

    public static void main(String[] args) {

        LargestPerimeter example = new LargestPerimeter();

          // Test with different input arrays

        int[] num1 = {3, 6, 2, 3};

        int[] num2 = {5, 8, 12, 3, 9};

        long result1 = example.largestPerimeter(num1);

        long result2 = example.largestPerimeter(num2);

        System.out.println("Largest perimeter for num1: " + result1);

        System.out.println("Largest perimeter for num2: " + result2);

    }

}

Output:

Largest perimeter: 8

Largest perimeter: 29

Complexity Analysis:

Time Complexity: The time complexity of a program is O(n log n) for sorting
Space Complexity: The space complexity of a program is O(n) for prefix sum

Approach 2: Preventing Extra Space

The improved approach computes the array's element sum up front. In order to quickly find possible polygon sides, it sorts the array. To ensure polygon correctness, it iterates backward and determines if the sum of the remaining elements is more than the current element. The approach removes the requirement for a separate prefix sum array while simultaneously improving time and space complexities.

Filename: PolygonLP.java

import java.util.Arrays;

public class PolygonLP {

    public static void main(String[] args) {

        int[] sides = {1, 3, 5, 7, 9};

        PolygonLP polygon = new PolygonLP();

        long largestPerimeter = polygon.largestPerimeter(sides);

        System.out.println("Largest Perimeter: " + largestPerimeter);

    }

       public long largestPerimeter(int[] num) {

        int n = num.length;

        if (n < 3) {

            return -1;

        }

        long sum = Arrays.stream(num).sum(); // Calculate the total sum of side lengths

        Arrays.sort(num); // Sort the array in ascending order

        long peri = -1;

        for (int i = n - 1; i >= 2; i--) {

            if (sum - num[i] > num[i - 1] + num[i - 2]) {

                peri = Math.max(peri, sum - num[i] + num[i - 1] + num[i - 2]);

                break;

            }

            sum -= num[i];

        }

        return peri;

    }

}

Output:

Largest perimeter = 28

Complexity Analysis:
Time Complexity: Since the sorting algorithm is O(n log n), the sorting step accounts for the majority of the program's overall time complexity.
Space Complexity: The space complexity of a program is O(1) since no extra space is introduced.

← Prev Next →