702870. Form a Triangle
Form a Triangle
Slug: form-a-triangle5935 Difficulty: Easy Id: 702870 Topic Tags: Arrays, Mathematical, Data Structures, Algorithms Company Tags: None
Summary
Given an array of three integers, determine if it is possible to form a triangle with the given side lengths. A triangle can be formed if the sum of the lengths of any two sides is greater than or equal to the length of the third side.
Detailed Explanation
To solve this problem, we need to check if the given triplet of numbers satisfies the condition for forming a triangle. The condition states that the sum of the lengths of any two sides must be greater than or equal to the length of the third side.
We can achieve this by sorting the array and then checking if the difference between the largest number (the longest side) and the middle number is less than or equal to the smallest number (the shortest side). If it is, then a triangle cannot be formed. Otherwise, we can form a triangle.
Here's the step-by-step breakdown of the solution:
- Sort the array in ascending order.
- Check if the difference between the largest number and the middle number is less than or equal to the smallest number. If it is, return false (triangle cannot be formed).
- Return true (triangle can be formed).
Time complexity: O(n log n) due to sorting Space complexity: O(1)
Optimized Solutions
Java
public boolean formTriangle(int[] arr) {
Arrays.sort(arr);
if (arr[2] - arr[1] <= arr[0]) {
return false;
}
return true;
}