Scale Engineer

Largest Perimeter Triangle

Easy
#0930Time: 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: O(1), as we only use a constant amount of extra space for variables.1 company
Patterns
MathGreedy
Algorithms
Sorting
Data structures
Array
Companies
Tesla

Prompt

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 <= 104
  • 1 <= nums[i] <= 106

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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:

  1. Initialize a variable maxPerimeter to 0.
  2. Use three nested loops to pick three distinct indices i, j, and k from the array.
  3. For each triplet of numbers (nums[i], nums[j], nums[k]), check if they satisfy all three conditions of the triangle inequality.
  4. If they form a valid triangle, calculate their sum (perimeter) and update maxPerimeter if this new perimeter is larger than the current maxPerimeter.
  5. 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

Time

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

O(1), as we only use a constant amount of extra space for variables.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem