LeetCode 3024 - Type of Triangle

The problem gives an integer array nums of length 3, where each value represents the length of a side of a possible triangle. Our task is to determine what kind of triangle these three sides can form.

leetcodeeasyarraymathsorting

LeetCode Problem 3024

Difficulty: 🟢 Easy
Topics: Array, Math, Sorting

Solution

Problem Understanding

The problem gives an integer array nums of length 3, where each value represents the length of a side of a possible triangle. Our task is to determine what kind of triangle these three sides can form.

There are four possible outputs:

  • "equilateral" if all three sides are equal
  • "isosceles" if exactly two sides are equal
  • "scalene" if all three sides are different
  • "none" if the three sides cannot form a valid triangle

The key mathematical condition is the triangle inequality theorem. For three side lengths a, b, and c to form a valid triangle:

  • a + b > c
  • a + c > b
  • b + c > a

If any of these conditions fail, the sides cannot form a triangle.

Since the array size is fixed at exactly 3, the input is extremely small. The constraints tell us:

  • nums.length == 3
  • 1 <= nums[i] <= 100

This means efficiency is not a major concern, because every solution will effectively run in constant time. However, we still want a clean and logically correct implementation.

There are a few important edge cases to think about:

  • Sides like [1,1,2] fail the triangle inequality because 1 + 1 == 2, which is not strictly greater.
  • Arrays where all sides are equal should immediately return "equilateral" after validating the triangle.
  • Arrays with two equal sides can either be valid isosceles triangles or invalid triangles, depending on the inequality condition.
  • Sorting the sides can simplify the triangle validity check because we only need to verify the two smaller sides against the largest side.

Approaches

Brute Force Approach

A brute force solution directly checks all three triangle inequality conditions one by one. After confirming the triangle is valid, we compare the side lengths to determine the triangle type.

The steps are:

  1. Extract the three side lengths.
  2. Check all three triangle inequalities.
  3. If any fail, return "none".
  4. Otherwise:
  • If all three sides are equal, return "equilateral".
  • If exactly two sides are equal, return "isosceles".
  • Otherwise, return "scalene".

This works correctly because the triangle inequality theorem completely determines whether the sides can form a triangle.

Although this is called a brute force approach, the input size is fixed, so it still runs in constant time.

Optimal Approach

A cleaner approach is to sort the array first.

After sorting:

a <= b <= c

For a sorted triangle, we only need to check:

a + b > c

Why is this enough?

Because c is the largest side. If the two smaller sides together are larger than the largest side, then the other two inequalities automatically hold.

After validating the triangle, we classify the triangle by counting equal sides:

  • Three equal sides → "equilateral"
  • Two equal sides → "isosceles"
  • All distinct → "scalene"

This solution is simpler and easier to reason about.

Approach Time Complexity Space Complexity Notes
Brute Force O(1) O(1) Checks all three triangle inequalities explicitly
Optimal O(1) O(1) Sorts the three numbers and uses one inequality check

Algorithm Walkthrough

  1. Sort the array of side lengths.

Sorting ensures the sides are ordered from smallest to largest. Let the sorted values be:

a <= b <= c

This makes the triangle validity check simpler. 2. Check whether the sides can form a valid triangle.

A valid triangle must satisfy:

a + b > c

Since c is the largest side, this single condition guarantees the triangle inequality holds for all three combinations.

If the condition fails, return "none" immediately. 3. Check whether all three sides are equal.

If:

a == b == c

then the triangle is equilateral. 4. Check whether exactly two sides are equal.

If any pair matches:

a == b or b == c

then the triangle is isosceles. 5. Otherwise, all three sides are different.

Return "scalene".

Why it works

The correctness relies on two properties.

First, sorting guarantees that the last element is the largest side. Therefore, checking whether the sum of the two smaller sides exceeds the largest side is sufficient to determine triangle validity.

Second, triangle classification depends entirely on how many equal side lengths exist:

  • Three equal sides define an equilateral triangle.
  • Exactly two equal sides define an isosceles triangle.
  • No equal sides define a scalene triangle.

Since the algorithm checks validity first and then classifies based on equality relationships, it always produces the correct result.

Python Solution

from typing import List

class Solution:
    def triangleType(self, nums: List[int]) -> str:
        nums.sort()

        # Check triangle validity
        if nums[0] + nums[1] <= nums[2]:
            return "none"

        # All sides equal
        if nums[0] == nums[1] == nums[2]:
            return "equilateral"

        # Exactly two sides equal
        if nums[0] == nums[1] or nums[1] == nums[2]:
            return "isosceles"

        # All sides different
        return "scalene"

The implementation starts by sorting the array so the largest side is always at index 2. This simplifies the triangle validity check to a single comparison.

The next section checks whether the triangle inequality holds. If the sum of the two smaller sides is less than or equal to the largest side, the sides cannot form a triangle, so the function immediately returns "none".

Once validity is confirmed, the code determines the triangle type. The equality checks are ordered carefully:

  • First check for all three equal sides.
  • Then check for exactly two equal sides.
  • Otherwise, the triangle must be scalene.

Because the input size is fixed at three elements, the implementation is concise and efficient.

Go Solution

package main

import "sort"

func triangleType(nums []int) string {
	sort.Ints(nums)

	// Check triangle validity
	if nums[0]+nums[1] <= nums[2] {
		return "none"
	}

	// All sides equal
	if nums[0] == nums[1] && nums[1] == nums[2] {
		return "equilateral"
	}

	// Exactly two sides equal
	if nums[0] == nums[1] || nums[1] == nums[2] {
		return "isosceles"
	}

	// All sides different
	return "scalene"
}

The Go solution follows the same logic as the Python implementation. The main difference is the use of sort.Ints(nums) to sort the slice in place.

Since the side lengths are very small integers, integer overflow is not a concern. The function also assumes the input length is always 3, which is guaranteed by the problem constraints.

Worked Examples

Example 1

Input:

nums = [3,3,3]

Step 1: Sort the array

Original Sorted
[3,3,3] [3,3,3]

Step 2: Check triangle validity

3 + 3 > 3
6 > 3

The triangle is valid.

Step 3: Check triangle type

Condition Result
nums[0] == nums[1] == nums[2] true

Return:

"equilateral"

Example 2

Input:

nums = [3,4,5]

Step 1: Sort the array

Original Sorted
[3,4,5] [3,4,5]

Step 2: Check triangle validity

3 + 4 > 5
7 > 5

The triangle is valid.

Step 3: Check triangle type

Condition Result
All equal false
Two equal false

Since all sides are different, return:

"scalene"

Additional Example

Input:

nums = [1,1,2]

Step 1: Sort the array

Original Sorted
[1,1,2] [1,1,2]

Step 2: Check triangle validity

1 + 1 > 2
2 > 2

This is false because equality is not enough.

Return:

"none"

Complexity Analysis

Measure Complexity Explanation
Time O(1) The array always contains exactly 3 elements
Space O(1) Only a constant amount of extra memory is used

Even though sorting is technically O(n log n), the array size is fixed at 3, so the runtime is effectively constant. The algorithm performs only a few comparisons after sorting.

Test Cases

sol = Solution()

# Provided examples
assert sol.triangleType([3, 3, 3]) == "equilateral"  # all sides equal
assert sol.triangleType([3, 4, 5]) == "scalene"      # all sides different

# Invalid triangles
assert sol.triangleType([1, 1, 2]) == "none"         # equality fails triangle inequality
assert sol.triangleType([1, 2, 3]) == "none"         # cannot form triangle
assert sol.triangleType([2, 2, 4]) == "none"         # degenerate triangle

# Isosceles triangles
assert sol.triangleType([5, 5, 8]) == "isosceles"    # exactly two equal sides
assert sol.triangleType([7, 10, 7]) == "isosceles"   # unsorted input

# Scalene triangles
assert sol.triangleType([4, 5, 6]) == "scalene"      # valid scalene
assert sol.triangleType([2, 3, 4]) == "scalene"      # another valid scalene

# Boundary values
assert sol.triangleType([100, 100, 100]) == "equilateral"  # maximum values
assert sol.triangleType([1, 1, 1]) == "equilateral"        # minimum valid triangle

# Sorting verification
assert sol.triangleType([8, 5, 5]) == "isosceles"    # requires sorting
Test Why
[3,3,3] Validates equilateral detection
[3,4,5] Validates scalene detection
[1,1,2] Tests failed triangle inequality
[1,2,3] Another invalid triangle case
[2,2,4] Tests degenerate triangle
[5,5,8] Validates isosceles detection
[7,10,7] Ensures sorting handles unordered input
[4,5,6] Standard valid scalene triangle
[2,3,4] Additional scalene validation
[100,100,100] Tests upper constraint boundary
[1,1,1] Tests lower valid boundary
[8,5,5] Confirms sorting logic works correctly

Edge Cases

One important edge case is when the sum of two sides is exactly equal to the third side, such as [1,1,2]. A common bug is using >= instead of >. A triangle requires the sum to be strictly greater. The implementation correctly handles this with:

if nums[0] + nums[1] <= nums[2]:

which rejects degenerate triangles.

Another important case is unsorted input like [7,10,7]. Without sorting, checking only one inequality could produce incorrect results because the largest side may not be in a known position. By sorting first, the algorithm guarantees that nums[2] is the largest side, making the validity check reliable.

A third edge case is distinguishing equilateral from isosceles triangles. Since an equilateral triangle technically has at least two equal sides, checking the isosceles condition first would incorrectly classify [3,3,3] as "isosceles". The implementation avoids this by checking the equilateral condition before the isosceles condition.