LeetCode 3053 - Classifying Triangles by Lengths

The problem requires classifying triangles based on the lengths of their three sides, represented by the columns A, B, a

leetcodeeasydatabase

LeetCode Problem 3053

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem requires classifying triangles based on the lengths of their three sides, represented by the columns A, B, and C in the Triangles table. Each row in the table represents a potential triangle. The output should identify each triangle as one of four types: Equilateral, Isosceles, Scalene, or Not A Triangle.

A triangle is valid if the sum of any two sides is greater than the third side. If this condition is violated, it is Not A Triangle. If the triangle is valid, we determine its type based on side equality. An Equilateral triangle has all three sides equal, an Isosceles triangle has exactly two sides equal, and a Scalene triangle has all sides of different lengths.

The input guarantees integer side lengths and a primary key constraint on (A, B, C), which ensures no duplicate triangles. Edge cases include triangles with sides that do not satisfy the triangle inequality, triangles with zero-length sides, or all sides equal.

Approaches

A naive brute-force approach would check each row individually with multiple conditional statements to classify each triangle type. While this would work for small datasets, SQL allows us to handle this in a single query efficiently, without iteration. The key insight is that we can use a CASE statement in SQL to encode the classification rules and the triangle inequality directly.

By using the CASE statement, we check Equilateral first (all sides equal), then Isosceles (exactly two sides equal), then Scalene (all sides different and satisfy the triangle inequality), and finally Not A Triangle for any invalid triangle. This approach leverages SQL’s declarative power to classify all rows in a single scan.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Loop over each row, multiple if statements per row, works but verbose
Optimal O(n) O(1) Single SQL CASE statement handles all classifications in one pass

Algorithm Walkthrough

  1. Begin by selecting all rows from the Triangles table.

  2. Use a CASE statement to evaluate conditions in order:

  3. Check if A + B <= C or A + C <= B or B + C <= A. If true, classify as Not A Triangle because the triangle inequality is violated.

  4. Check if A = B AND B = C. If true, classify as Equilateral.

  5. Check if A = B OR B = C OR A = C. If true, classify as Isosceles.

  6. If none of the above conditions are met, classify as Scalene.

  7. Return the resulting classifications in a column named triangle_type.

This algorithm works because the CASE statement evaluates conditions in order. The triangle inequality check ensures invalid triangles are excluded first, preventing misclassification. Then the equality checks accurately classify valid triangles into the correct type.

Python Solution

Since this is a SQL-based problem, a Python solution would generally involve querying a database using SQLAlchemy or sqlite3, but for demonstration, here is how the SQL query can be used in Python:

sql_query = """
SELECT
    CASE
        WHEN A + B <= C OR A + C <= B OR B + C <= A THEN 'Not A Triangle'
        WHEN A = B AND B = C THEN 'Equilateral'
        WHEN A = B OR B = C OR A = C THEN 'Isosceles'
        ELSE 'Scalene'
    END AS triangle_type
FROM Triangles;
"""

This query can be executed using any Python database connector. The query uses a single pass over the table and applies the triangle classification rules declaratively.

Go Solution

For Go, the solution is also primarily SQL-based, and the query remains identical. The Go code would execute it using the database/sql package:

query := `
SELECT
    CASE
        WHEN A + B <= C OR A + C <= B OR B + C <= A THEN 'Not A Triangle'
        WHEN A = B AND B = C THEN 'Equilateral'
        WHEN A = B OR B = C OR A = C THEN 'Isosceles'
        ELSE 'Scalene'
    END AS triangle_type
FROM Triangles;
`

Execute this query using db.Query(query) and scan the results. The Go implementation does not differ in logic from the Python approach; the main difference is in database driver handling and result scanning.

Worked Examples

For the input:

A B C
20 20 23
20 20 20
20 21 22
13 14 30

The query evaluates as follows:

  1. Row (20, 20, 23): 20 + 20 > 23, valid. Two sides equal → Isosceles.
  2. Row (20, 20, 20): All sides equal → Equilateral.
  3. Row (20, 21, 22): All sides different, triangle inequality satisfied → Scalene.
  4. Row (13, 14, 30): 13 + 14 <= 30 → Not A Triangle.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row is evaluated once, and conditions are checked in constant time.
Space O(1) No extra space is required beyond the output column.

The time complexity is linear in the number of rows because each triangle is processed exactly once. Space complexity is constant since no additional data structures are needed beyond the output.

Test Cases

# Provided examples
assert classify_triangle(20, 20, 23) == "Isosceles"  # two sides equal
assert classify_triangle(20, 20, 20) == "Equilateral"  # all sides equal
assert classify_triangle(20, 21, 22) == "Scalene"  # all sides different
assert classify_triangle(13, 14, 30) == "Not A Triangle"  # invalid triangle

# Edge cases
assert classify_triangle(0, 0, 0) == "Not A Triangle"  # zero-length sides
assert classify_triangle(5, 5, 10) == "Not A Triangle"  # sum equals third side
assert classify_triangle(5, 5, 8) == "Isosceles"  # two sides equal, valid triangle
assert classify_triangle(3, 4, 5) == "Scalene"  # Pythagorean triangle, valid
Test Why
(20, 20, 23) Valid isosceles triangle
(20, 20, 20) Equilateral triangle
(20, 21, 22) Valid scalene triangle
(13, 14, 30) Triangle inequality violation
(0, 0, 0) Zero-length sides handled
(5, 5, 10) Edge case where sum equals third side
(5, 5, 8) Valid isosceles triangle
(3, 4, 5) Classic scalene triangle

Edge Cases

One important edge case is when one or more sides are zero. Since a triangle cannot have zero-length sides, the query correctly identifies this as Not A Triangle. Another edge case occurs when the sum of two sides equals the third side, which also violates the triangle inequality; the query handles this with the first condition in the CASE statement. Finally, an edge case is a very large triangle with integer side lengths near the database's integer limits; the addition in the inequality check could theoretically overflow, but most SQL engines handle large integers safely, or you can cast to a larger type if needed. These edge cases ensure that invalid triangles are never misclassified.