Largest Perimeter Triangle

EASY

Description

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

Example 1:

Input: nums = [2,1,2]
Output: 5
Explanation: You can form a triangle with three side lengths: 1, 2, and 2.

Example 2:

Input: nums = [1,2,1,10]
Output: 0
Explanation: 
You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

Constraints:

3 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁶

Approaches

Checkout 2 different approaches to solve Largest Perimeter Triangle. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Three Nested Loops

This approach involves checking every possible combination of three side lengths from the input array. We use three nested loops to select three distinct numbers. For each combination, we check if they can form a valid triangle using the Triangle Inequality Theorem.

Algorithm

Initialize maxPerimeter to 0.
Use three nested loops to iterate through all unique triplets (i, j, k).
Let the sides be a = nums[i], b = nums[j], c = nums[k].
Check if a, b, and c can form a valid triangle using the triangle inequality: a + b > c, a + c > b, and b + c > a.
If they form a valid triangle, update maxPerimeter = max(maxPerimeter, a + b + c).
Return maxPerimeter after the loops complete.

The Triangle Inequality Theorem states that for three side lengths a, b, and c to form a triangle, the sum of the lengths of any two sides must be greater than the length of the third side (a + b > c, a + c > b, and b + c > a).

The algorithm proceeds as follows:

Initialize a variable maxPerimeter to 0.
Use three nested loops to pick three distinct indices i, j, and k from the array.
For each triplet of numbers (nums[i], nums[j], nums[k]), check if they satisfy all three conditions of the triangle inequality.
If they form a valid triangle, calculate their sum (perimeter) and update maxPerimeter if this new perimeter is larger than the current maxPerimeter.
After checking all possible triplets, the value stored in maxPerimeter is the answer. If no triangle could be formed, it will remain 0.

class Solution {
    public int largestPerimeter(int[] nums) {
        int n = nums.length;
        int maxPerimeter = 0;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    int a = nums[i];
                    int b = nums[j];
                    int c = nums[k];
                    if (a + b > c && a + c > b && b + c > a) {
                        maxPerimeter = Math.max(maxPerimeter, a + b + c);
                    }
                }
            }
        }
        return maxPerimeter;
    }
}

Complexity Analysis

Time Complexity: O(n^3), where n is the number of elements in `nums`. This is because of the three nested loops required to check every combination of three sides.Space Complexity: O(1), as we only use a constant amount of extra space for variables.

Pros and Cons

Pros:

Simple to understand and implement.
Correctly solves the problem for small inputs.

Cons:

Very inefficient due to its cubic time complexity.
Will likely result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Largest Perimeter Triangle. Click on different languages to view the code.

class Solution { public int largestPerimeter ( int [] nums ) { Arrays . sort ( nums ); for ( int i = nums . length - 1 ; i >= 2 ; -- i ) { int c = nums [ i - 1 ] + nums [ i - 2 ]; if ( c > nums [ i ]) { return c + nums [ i ]; } } return 0 ; } }

Video Solution

Watch the video walkthrough for Largest Perimeter Triangle

Algorithms:

Sorting

Patterns:

MathGreedy

Data Structures:

Array

Companies:

Tesla |