Problem Informations

• Problem Index: 3024
• Problem Link: Type of Triangle
• Topics: Array, Math, Sorting

Problem Description

You are given a 0-indexed integer array nums of size 3 which can form the sides of a triangle.

• A triangle is called equilateral if it has all sides of equal length.
• A triangle is called isosceles if it has exactly two sides of equal length.
• A triangle is called scalene if all its sides are of different lengths.

Return a string representing the type of triangle that can be formed or "none" if it cannot form a triangle.

Example 1:

Input: nums = [3,3,3]
Output: "equilateral"
Explanation: Since all the sides are of equal length, therefore, it will form an equilateral triangle.

Example 2:

Input: nums = [3,4,5]
Output: "scalene"
Explanation: 
nums[0] + nums[1] = 3 + 4 = 7, which is greater than nums[2] = 5.
nums[0] + nums[2] = 3 + 5 = 8, which is greater than nums[1] = 4.
nums[1] + nums[2] = 4 + 5 = 9, which is greater than nums[0] = 3. 
Since the sum of the two sides is greater than the third side for all three cases, therefore, it can form a triangle.
As all the sides are of different lengths, it will form a scalene triangle.

Constraints:

• nums.length == 3
• $1 \leq nums[i] \leq 100$

Intuition

The problem requires determining the type of triangle formed by three given side lengths. Triangles can be classified based on side equality: equilateral (all sides equal), isosceles (two sides equal), and scalene (all sides different). Additionally, a set of lengths may not always form a triangle if they don’t satisfy the triangle inequality theorem. Therefore, my initial thought is to use these properties to identify the type of triangle or ascertain if a valid triangle cannot be formed.

Approach

To solve the problem, the following steps are undertaken:

1. Sorting the sides: We begin by sorting the array of side lengths. This simplifies the task of checking the triangle inequality theorem, which states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side. Sorting allows a straightforward check of this condition with the sides in increasing order.

2. Checking triangle validity: After sorting, we verify if the sides can form a valid triangle using the triangle inequality theorem. Specifically, if the sum of the two smaller sides is not greater than the largest side (sides[0] + sides[1] <= sides[2]), then these sides cannot form a triangle, and we return “none”.

3. Categorizing the triangle:

   • Equilateral: If all three sides are equal (sides[0] == sides[1] == sides[2]), the triangle is identified as equilateral.
   • Isosceles: If only two sides are equal (sides[0] == sides[1], sides[1] == sides[2], or sides[0] == sides[2]), it is an isosceles triangle.
   • Scalene: If none of the sides are equal, the triangle is scalene.

This approach efficiently determines the type of triangle in constant time due to the fixed input size of three sides, facilitating a straightforward application of geometric principles and case analysis.

Code

C++

class Solution {
public:
    string triangleType(vector<int>& sides) {
        // Sort the sides to simplify the comparison logic
        sort(sides.begin(), sides.end());
        
        // Check if the given sides can form a triangle
        // This follows the triangle inequality theorem
        if (sides[0] + sides[1] <= sides[2]) {
            return "none"; // Not a valid triangle
        }
        
        // Check for equilateral triangle: all sides are equal
        if (sides[0] == sides[1] && sides[1] == sides[2]) {
            return "equilateral";
        }
        
        // Check for isosceles triangle: exactly two sides are equal
        if (sides[0] == sides[1] || sides[1] == sides[2] || sides[0] == sides[2]) {
            return "isosceles";
        }
        
        // If none of the above, it must be a scalene triangle: all sides are different
        return "scalene";
    }
};

Python

class Solution:
    def triangleType(self, sides):
        # Sort the sides to simplify the comparison logic
        sides.sort()
        
        # Check if the given sides can form a triangle
        # This follows the triangle inequality theorem
        if sides[0] + sides[1] <= sides[2]:
            return "none"  # Not a valid triangle
        
        # Check for equilateral triangle: all sides are equal
        if sides[0] == sides[1] and sides[1] == sides[2]:
            return "equilateral"
        
        # Check for isosceles triangle: exactly two sides are equal
        if sides[0] == sides[1] or sides[1] == sides[2] or sides[0] == sides[2]:
            return "isosceles"
        
        # If none of the above, it must be a scalene triangle: all sides are different
        return "scalene"

Complexity

• Time complexity: $O(1)$

  The code operates on an input array sides with a fixed size of 3, as specified by the problem constraints. The sort operation typically has a time complexity of $O(n \log n)$ for an input of size $n$, but since $n$ is a constant (3 in this case), it effectively becomes $O(1)$. All subsequent operations involve simple arithmetic and comparisons, which are constant-time operations. Thus, the overall time complexity remains $O(1)$.

• Space complexity: $O(1)$

  The space complexity is $O(1)$ because the algorithm only uses a constant amount of extra space. No additional data structures are used beyond the input array, and the operations performed do not require additional space that grows with the input size.