LeetCode 3899 - Angles of a Triangle

LeetCode Problem 3899

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

We are given an array sides containing exactly three positive integers. Each integer represents the length of one side of a potential triangle.

The task is to determine whether these three side lengths can form a triangle with positive area. A triangle exists if and only if the triangle inequality holds. For three sides a, b, and c, this means:

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

Since there are only three sides, it is common to sort them and simply check whether the sum of the two smaller sides is strictly greater than the largest side. If equality holds, the points lie on a straight line and the area is zero, which is not allowed.

If a valid triangle exists, we must compute its three internal angles in degrees and return them sorted in non-decreasing order. The angles can be obtained using the Law of Cosines.

The input size is extremely small because sides.length == 3. Therefore, efficiency is not a concern. The main challenge is correctly applying geometric formulas and handling floating-point calculations.

Several edge cases are important:

• Degenerate triangles such as [2,4,2], where the sum of two sides equals the third, must return an empty array.
• Equilateral triangles such as [5,5,5] should produce three angles of exactly 60 degrees.
• Isosceles triangles should correctly produce two equal angles.
• Very large valid side lengths near the constraint limit must still be handled accurately.
• Floating-point rounding errors should not cause invalid values to be passed into acos.

Approaches

Brute Force Approach

A brute-force perspective is to first verify every triangle inequality individually. If the triangle is valid, compute each angle independently using the Law of Cosines.

For example, for angle opposite side a:

$$\cos(A)=\frac{b^2+c^2-a^2}{2bc}$$

Then compute:

$$A=\arccos(\cos(A))$$

Repeat for all three angles, convert them to degrees, sort them, and return the result.

This approach is correct because the Law of Cosines uniquely determines the angles of a triangle from its side lengths.

Since there are only three sides, the computation is effectively constant time.

Optimal Approach

The key observation is that there are only three values. Once the triangle inequality is verified, the Law of Cosines directly gives all three angles.

No searching, dynamic programming, graph traversal, or advanced geometry is required. The entire problem reduces to:

1. Verify the triangle exists.
2. Compute the three angles.
3. Convert to degrees.
4. Sort the results.

This is already optimal because every side must be examined at least once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1)	O(1)	Check inequalities and compute all three angles directly
Optimal	O(1)	O(1)	Sort sides, validate triangle, compute angles via Law of Cosines

Algorithm Walkthrough

1. Extract the three side lengths a, b, and c from the input.
2. Sort the side lengths. Let the sorted values be x ≤ y ≤ z.
3. Check the triangle inequality. Since the sides are sorted, it is sufficient to verify whether x + y > z.
4. If the inequality fails, return an empty array because no positive-area triangle can be formed.
5. Compute each angle using the Law of Cosines.

For the angle opposite side a:

$$\cos(A)=\frac{b^2+c^2-a^2}{2bc}$$

Similarly compute cos(B) and cos(C). 6. Clamp each cosine value into the interval [-1, 1]. This protects against tiny floating-point inaccuracies that could otherwise make acos fail. 7. Apply acos to obtain the angles in radians. 8. Convert radians to degrees. 9. Store the three angles in an array. 10. Sort the angle array in non-decreasing order. 11. Return the sorted angle array.

Why it works

The triangle inequality is a necessary and sufficient condition for three side lengths to form a positive-area triangle. Once a valid triangle exists, the Law of Cosines uniquely determines each internal angle from the side lengths. Therefore, the algorithm computes exactly the three angles of the triangle. Sorting them before returning satisfies the output requirement.

Python Solution

class Solution:
    def internalAngles(self, sides: list[int]) -> list[float]:
        import math

        x, y, z = sorted(sides)

        if x + y <= z:
            return []

        a, b, c = map(float, sides)

        def angle(opposite: float, side1: float, side2: float) -> float:
            cos_value = (
                side1 * side1 +
                side2 * side2 -
                opposite * opposite
            ) / (2.0 * side1 * side2)

            cos_value = max(-1.0, min(1.0, cos_value))

            return math.degrees(math.acos(cos_value))

        angles = [
            angle(a, b, c),
            angle(b, a, c),
            angle(c, a, b),
        ]

        angles.sort()
        return angles

The implementation begins by sorting the side lengths and checking the triangle inequality. If the triangle is invalid, an empty list is returned immediately.

The helper function angle() implements the Law of Cosines. It receives the side opposite the desired angle and the two adjacent sides. After computing the cosine value, it clamps the result into the valid domain of acos, preventing floating-point issues.

Each of the three angles is computed independently, converted to degrees, collected into a list, sorted, and returned.

Go Solution

package main

import (
	"math"
	"sort"
)

func internalAngles(sides []int) []float64 {
	sortedSides := append([]int(nil), sides...)
	sort.Ints(sortedSides)

	if sortedSides[0]+sortedSides[1] <= sortedSides[2] {
		return []float64{}
	}

	a := float64(sides[0])
	b := float64(sides[1])
	c := float64(sides[2])

	angle := func(opposite, side1, side2 float64) float64 {
		cosValue := (side1*side1 + side2*side2 - opposite*opposite) /
			(2.0 * side1 * side2)

		if cosValue < -1.0 {
			cosValue = -1.0
		}
		if cosValue > 1.0 {
			cosValue = 1.0
		}

		return math.Acos(cosValue) * 180.0 / math.Pi
	}

	angles := []float64{
		angle(a, b, c),
		angle(b, a, c),
		angle(c, a, b),
	}

	sort.Float64s(angles)
	return angles
}

The Go implementation follows the same logic as the Python version. A copy of the input slice is sorted to perform the triangle validity check. Floating-point calculations use float64, and the cosine values are clamped before calling math.Acos. An empty slice is returned for invalid triangles.

Worked Examples

Example 1

Input

sides = [3,4,5]

Step 1: Sort

Variable	Value
x	3
y	4
z	5

Step 2: Triangle Check

Expression	Value
x + y	7
z	5
7 > 5	True

The triangle is valid.

Step 3: Compute Angles

Opposite Side	Cosine Formula Result	Angle
3	0.8	36.869897646°
4	0.6	53.130102354°
5	0.0	90.000000000°

Step 4: Sort

Angles
36.869897646
53.130102354
90.000000000

Output

[36.86990,53.13010,90.00000]

Example 2

Input

sides = [2,4,2]

Step 1: Sort

Variable	Value
x	2
y	2
z	4

Step 2: Triangle Check

Expression	Value
x + y	4
z	4
4 > 4	False

The triangle is degenerate and has zero area.

Output

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only three sides and three angle computations
Space	O(1)	Uses a constant amount of extra storage

Because the input size is fixed at exactly three elements, all operations take constant time. Sorting three values is also constant time. No auxiliary data structures grow with input size.

Test Cases

import math

s = Solution()

# Provided examples
assert len(s.internalAngles([3, 4, 5])) == 3  # classic right triangle
assert s.internalAngles([2, 4, 2]) == []      # degenerate triangle

# Equilateral triangle
angles = s.internalAngles([5, 5, 5])
assert all(abs(a - 60.0) < 1e-5 for a in angles)  # all angles 60

# Isosceles triangle
angles = s.internalAngles([5, 5, 8])
assert len(angles) == 3  # valid isosceles triangle

# Smallest valid triangle
angles = s.internalAngles([1, 1, 1])
assert all(abs(a - 60.0) < 1e-5 for a in angles)  # minimum equal sides

# Boundary invalid case
assert s.internalAngles([1, 1, 2]) == []  # exactly degenerate

# Large valid sides
angles = s.internalAngles([1000, 1000, 1000])
assert len(angles) == 3  # large equilateral

# Scalene triangle
angles = s.internalAngles([7, 8, 9])
assert len(angles) == 3  # general valid triangle

# Nearly degenerate but valid
angles = s.internalAngles([999, 999, 1000])
assert len(angles) == 3  # tests numerical stability

# Another right triangle
angles = s.internalAngles([5, 12, 13])
assert abs(angles[-1] - 90.0) < 1e-5  # right angle present

Test	Why
[3,4,5]	Standard right triangle
[2,4,2]	Degenerate triangle, must return empty
[5,5,5]	Equilateral triangle
[5,5,8]	Isosceles triangle
[1,1,1]	Smallest equal valid sides
[1,1,2]	Triangle inequality boundary
[1000,1000,1000]	Maximum constraint values
[7,8,9]	General scalene triangle
[999,999,1000]	Near-degenerate valid case
[5,12,13]	Another right triangle

Edge Cases

A degenerate triangle is one of the most important edge cases. For example, [2,4,2] satisfies 2 + 2 = 4. Geometrically, the three points lie on a straight line and the area is zero. The problem explicitly requires a positive-area triangle. The implementation handles this by checking x + y <= z after sorting.

An equilateral triangle such as [5,5,5] can expose mistakes in angle calculations. All three angles should be exactly 60 degrees. Since the Law of Cosines is applied symmetrically to all sides, the implementation correctly computes three identical angles.

Near-degenerate triangles such as [999,999,1000] can produce cosine values extremely close to the limits of the valid range for acos. Floating-point rounding may generate values slightly above 1 or below -1, which would cause a domain error. The implementation prevents this by clamping every cosine value into [-1, 1] before calling acos.

Another important case is a right triangle such as [3,4,5]. The largest angle should be exactly 90 degrees. The Law of Cosines naturally produces a cosine value of zero for the angle opposite side 5, yielding the correct result after conversion to degrees.