Type of Triangle

#694 Most AskedEasy

Type of Triangle #694 Most Asked

Easy

Microsoft

2 views

Topics:

Arrays

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 <= nums[i] <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What data type are the side lengths? Can they be floating-point numbers or are they always integers?
Can any of the side lengths be zero or negative?
What should I return if the given side lengths cannot form a valid triangle (e.g., violate the triangle inequality theorem)?
Is the order of the side lengths significant? In other words, is a triangle with sides (3, 4, 5) considered different from a triangle with sides (5, 4, 3)?
Are there any limits on the maximum value of the side lengths that I should be aware of?

Brute Force Solution

Approach

The brute force approach to determining the type of triangle involves checking every possible combination of side lengths against all triangle type conditions. It's like testing every single possibility to see if it fits the rules. We need to check against what defines an equilateral, isosceles, or scalene triangle.

Here's how the algorithm would work step-by-step:

Get the lengths of the three sides of the triangle.
Check if all three sides are equal. If they are, it's an equilateral triangle.
If it's not equilateral, check if at least two sides are equal. If they are, it's an isosceles triangle.
If it's not equilateral or isosceles, then all three sides must be different, meaning it's a scalene triangle.

Code Implementation

def type_of_triangle(side_one, side_two, side_three): 
    # Check if all sides are equal; then it's equilateral
    if side_one == side_two == side_three:
        return "equilateral"

    # If not equilateral, check if any two sides are equal; then it's isosceles
    if side_one == side_two or side_one == side_three or side_two == side_three:
        return "isosceles"

    # If none of the above are true, then no sides are equal; scalene
    return "scalene"

Big(O) Analysis

Time Complexity

O(1) – The input consists of three side lengths. The algorithm performs a fixed number of comparisons: one to check for equilateral, one to check for isosceles if it’s not equilateral. Because the number of operations is independent of an arbitrarily large input size n, and is capped at a constant number of checks, the time complexity is O(1).

Space Complexity

O(1) – The provided approach for determining the type of triangle involves only comparing the lengths of the three sides, which are already provided as input. No additional data structures, such as arrays, lists, or hash maps, are created or used during the process. The space used is constant regardless of the side lengths, as we're only using a few variables to store the side lengths and perform comparisons. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To determine the type of triangle, we need to analyze the lengths of its sides. The most efficient approach involves sorting the side lengths first, and then applying the Pythagorean theorem and checking for equality to determine the triangle type.

Here's how the algorithm would work step-by-step:

First, take the three given side lengths and arrange them from smallest to largest.
Next, check if the sum of the two smallest side lengths is greater than the largest side length. If not, it's not a triangle.
If it is a triangle, determine if it's a right triangle by checking if the square of the largest side equals the sum of the squares of the other two sides.
If it's a right triangle, we're done. Otherwise, check if it's an acute triangle by seeing if the square of the largest side is less than the sum of the squares of the other two sides. If it is, it's acute.
If it's not right or acute, then it must be an obtuse triangle, meaning that the square of the largest side is greater than the sum of the squares of the other two sides.
Finally, check for equality. If all three sides are equal, it's an equilateral triangle. If exactly two sides are equal, it's an isosceles triangle. If no sides are equal, it's a scalene triangle.
Combine the type from right/acute/obtuse with the equilateral/isosceles/scalene property to classify the triangle.

Code Implementation

def type_of_triangle(side_one, side_two, side_three):
    sides = sorted([side_one, side_two, side_three])
    smallest_side = sides[0]
    middle_side = sides[1]
    largest_side = sides[2]

    if smallest_side + middle_side <= largest_side:
        return "Not a triangle"

    # Determine if it is a right, acute, or obtuse triangle
    if largest_side**2 == smallest_side**2 + middle_side**2:
        triangle_type = "Right"
    elif largest_side**2 < smallest_side**2 + middle_side**2:
        triangle_type = "Acute"
    else:
        triangle_type = "Obtuse"

    # Determine if it is equilateral, isosceles, or scalene.
    if side_one == side_two == side_three:
        side_type = "Equilateral"
    elif side_one == side_two or side_one == side_three or side_two == side_three:
        side_type = "Isosceles"
    else:
        side_type = "Scalene"

    # Combine the two classifications
    if side_type == "Equilateral":
        return "Equilateral"
    else:
        return triangle_type + " " + side_type

Big(O) Analysis

Time Complexity

O(n log n) – The primary driver of the time complexity is the sorting of the three side lengths. Although the input size is fixed at three, the sorting operation generally takes O(n log n) time for n elements. In this specific case, where n=3, sorting takes constant time, but we express the complexity more generically as O(n log n) because this approach would apply to a larger problem if the side lengths weren't initially provided in any order. Checking the triangle inequality and other conditions (right, acute, obtuse, equilateral, isosceles, scalene) all take constant time, so they do not affect the overall complexity. Thus, the overall time complexity is dominated by the sorting step, approximating O(n log n).

Space Complexity

O(1) – The algorithm primarily uses a fixed number of variables to store the side lengths (after potentially sorting, although in-place sorting can be assumed) and intermediate calculations such as squared values. No auxiliary data structures that scale with the input size (N, the number of sides which is fixed at 3) are used. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
One or more sides are zero	Treat zero as invalid side length and return 'Not a triangle'.
One or more sides are negative	Treat negative as invalid side length and return 'Not a triangle'.
Input sides violate triangle inequality (a + b <= c)	Return 'Not a triangle' if the sum of any two sides is not greater than the third side.
Sides are extremely large numbers leading to potential overflow during calculations	Use appropriate data types (e.g., long) to avoid integer overflow when calculating side lengths or comparison values, or use a different approach if overflow is still a concern.
Sides are floating-point numbers with potential precision issues	Use a small tolerance value (epsilon) when comparing floating-point numbers to account for precision errors.
All three sides are equal	Return 'Equilateral' since all sides have same length.
Two sides are equal	Check if two sides are equal, then check if it's also equilateral, return 'Isosceles'.
Sides are provided in an unexpected order or format	Sort the sides in ascending order for consistent comparison and easier triangle validity check.

One or more sides are zero

How to Handle:

Treat zero as invalid side length and return 'Not a triangle'.

One or more sides are negative

How to Handle:

Treat negative as invalid side length and return 'Not a triangle'.

Input sides violate triangle inequality (a + b <= c)

How to Handle:

Return 'Not a triangle' if the sum of any two sides is not greater than the third side.

Sides are extremely large numbers leading to potential overflow during calculations

How to Handle:

Use appropriate data types (e.g., long) to avoid integer overflow when calculating side lengths or comparison values, or use a different approach if overflow is still a concern.

Sides are floating-point numbers with potential precision issues

How to Handle:

Use a small tolerance value (epsilon) when comparing floating-point numbers to account for precision errors.

All three sides are equal

How to Handle:

Return 'Equilateral' since all sides have same length.

Two sides are equal

How to Handle:

Check if two sides are equal, then check if it's also equilateral, return 'Isosceles'.

Sides are provided in an unexpected order or format

How to Handle:

Sort the sides in ascending order for consistent comparison and easier triangle validity check.