976. Largest Perimeter Triangle
Problem Description
The problem requires us to look for the largest perimeter of a triangle that can be formed from an array of integers representing the lengths of the sides. A triangle can only exist if the sum of the lengths of any two sides is greater than the length of the third side. This is known as the triangle inequality theorem. If no such combination exists in the array, the function should return 0. A key aspect is to remember that we are looking for the largest possible perimeter, which implies that we should focus on the largest numbers in the array as they have the potential to contribute to a larger perimeter.
Intuition
The intuition behind the solution is rooted in the triangle inequality theorem mentioned above. We know that we can sort the array of side lengths in ascending order. Then, to build a triangle with the largest possible perimeter, we should start by trying to use the longest sides available. Once the array is sorted, we iterate from the end of the array towards the start, which allows us to always pick the three longest lengths available at any point.
In each iteration, we check if the current value and the two preceding values form a valid triangle. We make such a check by ensuring that the sum of the smaller two side lengths (located at i-1
and i-2
after sorting) is strictly greater than the largest side length (located at i
). If this condition is met, we can form a triangle with a non-zero area, and therefore, we calculate its perimeter by summing all three side lengths.
If we go through the entire array without finding three lengths that satisfy the triangle inequality, then it is not possible to form any triangle and the function returns 0.
Solution Approach
The implementation of the solution takes advantage of the Python's built-in sort()
method to sort the list of integers in ascending order. This approach simplifies the problem by allowing us to check the triangle inequality theorem starting with the largest values at the end of the sorted list.
Here's how the algorithm in the given solution works step by step:
-
First, we sort the
nums
list in place, so the smallest side lengths are at the start of the list and the largest at the end. -
We then iterate through the list in reverse using a
for
loop starting from the end (len(nums) - 1
) and moving towards the beginning, decrementing by one each time (i - 1
). By doing so, we are always considering the three longest side lengths available and checking their ability to form a valid triangle. -
In each iteration, we look at the three side lengths at
nums[i]
(the longest),nums[i - 1]
, andnums[i - 2]
(the shorter two). We assign the sum of the two shorter sides to a variablec
using the walrus operator (:=
), which is a feature introduced in Python 3.8 that assigns values to variables as part of an expression. -
We then check if the sum of the two shorter sides (
c
) is greater than the length of the longest side (nums[i]
). If this condition holds true, it means that a triangle can be formed, and we calculate the perimeter by adding the lengths of all three sides (c + nums[i]
). This value is immediately returned as it's guaranteed to be the largest possible perimeter we can find, given the sorted nature of the list and our iteration from largest to smallest. -
If no valid triangle is found during iteration, the loop completes without hitting a return statement. In that case, the code proceeds to the final
return 0
, indicating that no triangle could be formed from the given side lengths.
This solution is efficient because it minimizes the number of comparisons we need to make; it stops as soon as it finds a valid triangle, and because of the sorting, we know that's the largest perimeter possible.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach described, let's use a small example with the following array of integers representing the lengths of potential sides of a triangle:
nums = [2, 1, 2, 4, 3]
- According to the solution approach, we first sort this array in ascending order to arrange the potential side lengths from smallest to largest:
[1, 2, 2, 3, 4]
-
We will now iterate from the end of the sorted array towards the beginning to try and find the three longest sides that can form a triangle. So we start with the three values at the end of the array:
4
(the longest),3
, and2
(the shorter two). -
In the first iteration, the variables
i
,i - 1
, andi - 2
correspond to the lengths4
,3
, and2
respectively. We calculate the sum of the two shorter lengths and assign it to a variablec
.c := nums[i - 1] + nums[i - 2]
which becomesc := 3 + 2
, hencec = 5
. -
We now check if the sum of the shorter sides (
c = 5
) is greater than the length of the longest side (nums[i] = 4
). Since5
is greater than4
, these sides do indeed satisfy the triangle inequality theorem, and we can form a triangle. -
Since a valid triangle can be formed using these lengths, we calculate the perimeter:
perimeter = c + nums[i]
which becomesperimeter = 5 + 4
, henceperimeter = 9
. -
As this is the first set of sides checked from the largest values, we know it is the largest possible perimeter that can be formed. Therefore, we return this value without continuing the iteration.
In this example, the function would return 9
as the largest perimeter of a triangle that can be formed with the side lengths given in the initial array nums
. If the values continued to be unsuitable for forming a triangle (not satisfying the inequality theorem), we would continue the iteration until we either found a valid set of sides or reached the end of the array and returned 0
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def largestPerimeter(self, nums: List[int]) -> int:
5 # Sort the array to organize the sides of triangles from smallest to largest
6 nums.sort()
7
8 # Start from the end of the sorted array to find the largest possible triangle
9 for i in range(len(nums) - 1, 1, -1):
10 # Use the triangle inequality theorem, which states that the sum of the lengths
11 # of any two sides of a triangle must be greater than the length of the remaining side
12 # to check if a triangle can be formed with three sides
13 if nums[i - 1] + nums[i - 2] > nums[i]:
14 # If a valid triangle is found, return its perimeter
15 return nums[i - 1] + nums[i - 2] + nums[i]
16
17 # In case no valid triangle can be formed, return 0
18 return 0
19
1import java.util.Arrays; // Import Arrays class for the sort method.
2
3class Solution {
4 public int largestPerimeter(int[] nums) {
5
6 // Sort the array of side lengths in non-decreasing order.
7 Arrays.sort(nums);
8
9 // Traverse the sorted array in reverse to check for a valid triangle.
10 for (int i = nums.length - 1; i >= 2; --i) {
11 // For a non-degenerate triangle, the sum of the lengths of the two
12 // shorter sides (nums[i-2] and nums[i-1]) must be greater than
13 // the length of the longest side (nums[i]).
14 int sumOfShorterSides = nums[i - 2] + nums[i - 1];
15
16 // If the sum of the two shorter sides is greater than the longest side,
17 // a valid triangle can be formed, so return the perimeter of the triangle.
18 if (sumOfShorterSides > nums[i]) {
19 int perimeter = sumOfShorterSides + nums[i]; // Compute the perimeter of the triangle.
20 return perimeter; // Return the perimeter as this is the largest one found.
21 }
22
23 // If no valid triangle can be formed with the current triplet,
24 // the loop continues to check for a valid triangle with the
25 // next set of side lengths in the sorted array.
26 }
27
28 // If no valid triangle was found, return 0.
29 return 0;
30 }
31}
32
1#include <vector>
2#include <algorithm> // For std::sort
3
4class Solution {
5public:
6 // Function to find the largest perimeter of a triangle that can be formed with non-degenerate conditions
7 int largestPerimeter(std::vector<int>& nums) {
8 // Sort the array in non-descending order to prepare for the triangle inequality check
9 std::sort(nums.begin(), nums.end());
10
11 // Iterate over the array from the end to the beginning to check for possible triangles
12 for (int i = nums.size() - 1; i >= 2; --i) {
13 // Check the triangle inequality: sum of lengths of the shorter two sides should be greater than the length of the longest side
14 int shorterSidesSum = nums[i - 1] + nums[i - 2];
15 if (shorterSidesSum > nums[i]) {
16 // If a valid triangle can be formed, return the perimeter of the triangle
17 return shorterSidesSum + nums[i];
18 }
19 }
20
21 // If no valid triangle is found, return 0 as specified in the problem statement
22 return 0;
23 }
24};
25
1/**
2 * This function finds the largest perimeter of a triangle that can be formed with non-zero area,
3 * given an array of integer lengths.
4 * It returns 0 if no such triangle exists.
5 * The algorithm checks for the triangle inequality theorem which states that the sum of the lengths
6 * of any two sides of a triangle must be greater than or equal to the length of the remaining side.
7 *
8 * @param {number[]} sides - An array of numbers representing the lengths of the sides.
9 * @returns {number} The largest possible perimeter of the triangle with non-zero area, or 0 if no triangle can be formed.
10 */
11function largestPerimeter(sides: number[]): number {
12 // The length of the sides array.
13 const n = sides.length;
14
15 // Sort the array in non-increasing order.
16 sides.sort((a, b) => b - a);
17
18 // Iterate through the sides to find the largest perimeter where a triangle can be formed.
19 for (let i = 2; i < n; i++) {
20 // Get the three consecutive sides after sorting.
21 const sideA = sides[i - 2];
22 const sideB = sides[i - 1];
23 const sideC = sides[i];
24
25 // Check for the triangle inequality theorem.
26 if (sideA < sideB + sideC) {
27 // If it's a valid triangle, return the perimeter.
28 return sideA + sideB + sideC;
29 }
30 }
31
32 // If no valid triangle is found, return 0.
33 return 0;
34}
35
Time and Space Complexity
Time Complexity
The given function first sorts the array, which has a time complexity of O(n log n)
where n
is the number of elements in the input array nums
. After sorting, a for loop is used to iterate over the array in reverse order, beginning from the second-to-last element. This loop runs at most n
times in the worst case (if no suitable triplet is found until the start of the array). The combination of the sort operation followed by a linear scan leads to a total time complexity of O(n log n + n)
, which simplifies to O(n log n)
since the n log n
term dominates the linear term.
Space Complexity
The space complexity of the code is O(1)
since the sorting is done in place (not considering the space used by the sorting algorithm itself which may vary depending on the implementation, but for many standard algorithms like Timsort in Python, it is at worst O(n)
) and only a constant amount of extra space is used for variables such as i
and c
. Since these do not scale with the input size, the additional space requirement is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.