Last Updated: 15 Apr, 2021
Triangle with the largest perimeter
Easy
Asked in company
You are given an array of positive integers ‘ARR’ of size ‘N’. The task is to return the largest perimeter of a triangle with a non-zero area, having any three elements of ‘ARR’ as its sides. If it’s impossible to form such a triangle, return 0.
Example:
‘N’ = 4, and ‘ARR’ = [2, 3, 4, 2]
For a triangle, the largest side should be strictly less than the sum of the other two sides. The triplet [2, 2, 4] cannot form a triangle as ‘4 = 2 + 2’. Here, two valid triangles can be formed, having sides as:
1. [2, 3, 4], with perimeter ‘9’.
2. [2, 2, 3], with perimeter ‘7’.
So, you should return ‘9’ as the answer.
Note:
The array ‘ARR’ contains at least three integers, i.e., ‘N >= 3’.
Input format:
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.
The first line of each test case contains an integer ‘N’ denoting the size of the array ‘ARR’.
The second line of each test case contains ‘N’ integers representing the array ‘ARR’.
Output format:
For every test case, return the largest perimeter of a triangle that can be formed. If it’s impossible to form any triangle, return 0.
Note:
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= N <= 10^3
Value of each element of ‘ARR’ ranges from [1, 10^9].
Time limit: 1 sec
Approaches
Let’s say the lengths of three sides of a triangle are ‘A’, ‘B’, and ‘C’, with ‘A <= B <= C’. Then, the condition for these lengths to form a valid triangle with a non-zero area is ‘C < A + B’, i.e., the length of the largest side should be less than the sum of lengths of the other two sides.
Use a variable to keep track of the maximum perimeter, let’s say ‘RES’. We can use three nested loops over the array ‘ARR’ to generate all possible triangles. In the innermost loop, if the triangle is valid, then update ‘RES’ accordingly.
Algorithm:
- Create an array ‘CUR[3]’. Use it to store the triangle formed in the innermost loop.
- Set ‘RES = 0’. Use it to store the maximum perimeter.
- Run a loop where ‘i’ ranges from ‘0’ to ‘N - 3’:
- Run a loop where ‘j’ ranges from ‘i + 1’ to ‘N - 2’:
- Run a loop where ‘k’ ranges from ‘j + 1’ to ‘N - 1’:
- ‘CUR[0] = ARR[i]’.
- ‘CUR[1] = ARR[j]’.
- ‘CUR[2] = ARR[k]’.
- ‘sort(CUR)’. Sort the array in ascending order.
- If ‘CUR[2] < CUR[1] + CUR[0]’, then ‘CUR’ is a valid triangle:
- ‘RES = max(RES, CUR[0] + CUR[1] + CUR[2])’.
- Run a loop where ‘k’ ranges from ‘j + 1’ to ‘N - 1’:
- Run a loop where ‘j’ ranges from ‘i + 1’ to ‘N - 2’:
- Return ‘RES’ as the answer.
Let’s say the lengths of three sides of a triangle are ‘A’, ‘B’, and ‘C’, with ‘A <= B <= C’. Then, the condition for these lengths to form a valid triangle with a non-zero area is ‘C < A + B’.
If we already know ‘C’ and the largest possible ‘A’, ‘B’ such that ‘A <= B <= C’, then if ‘C >= A + B’, then we cannot form a triangle, also the values smaller than ‘A’ and ‘B’ will not form a triangle with ‘C’ either. Otherwise, if ‘C < A + B‘, then A + B + C’ will be the largest perimeter for a triangle with ‘C’ as the largest side.
So, we sort the array ‘ARR’ in descending order, and for every index ‘i’ (such that ‘i + 2 < n’) we have ‘C = ARR[i]’, ‘B = ARR[i + 1]’, and ‘A = ARR[i + 2]’. If ‘A’, ‘B’, and ‘C’ form a valid triangle, then this will be the largest perimeter, so return ‘A + B + C’ as the answer.
Algorithm:
- ‘sort(ARR)’. Sort the array in descending order.
- Run a loop where ‘i’ ranges from ‘0’ to ‘N - 3’:
- If ‘ARR[i] < ARR[i + 1] + ARR[i + 2]’, then this is a valid triangle:
- Return ‘ARR[i] + ARR[i + 1] + ARR[i + 2]’ as the answer.
- If ‘ARR[i] < ARR[i + 1] + ARR[i + 2]’, then this is a valid triangle:
- Return ‘0’ as it is impossible to form a valid triangle.