LeetCode 610 - Triangle Judgement

The problem is asking us to determine, for each row in a table called Triangle, whether the three given line segments can form a valid triangle. Each row contains three integers x, y, and z representing the lengths of the segments.

leetcodeeasydatabase

LeetCode Problem 610

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem is asking us to determine, for each row in a table called Triangle, whether the three given line segments can form a valid triangle. Each row contains three integers x, y, and z representing the lengths of the segments. The expected output is a new table that includes all original columns plus a triangle column with values Yes or No.

The core mathematical requirement is the triangle inequality: for three side lengths to form a triangle, the sum of any two sides must be strictly greater than the third side. In other words, a valid triangle must satisfy:

x + y > z
x + z > y
y + z > x

Constraints tell us that all rows are unique due to the primary key (x, y, z), so we do not need to worry about duplicates. Since the problem does not specify very large data limits, we can assume that a straightforward SQL check for the triangle inequality will perform adequately. Important edge cases include zero or negative side lengths (which cannot form a triangle) and rows where two sides sum exactly to the third (degenerate triangles, which should be considered invalid).

Approaches

The brute-force approach would involve selecting all rows and applying the triangle inequality in some procedural way. While simple, this is unnecessary for SQL because relational databases allow direct row-level computation.

The optimal approach is to use a SQL CASE WHEN statement to check the triangle inequality for each row. This is efficient because it computes the result directly during selection without additional iteration or joins.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Retrieve rows and apply triangle inequality procedurally
Optimal O(n) O(1) Use SQL CASE WHEN to evaluate each row inline

Algorithm Walkthrough

  1. Select from the Triangle table: We begin by querying all columns x, y, and z.
  2. Evaluate the triangle condition: For each row, use the triangle inequality. Check if x + y > z, x + z > y, and y + z > x.
  3. Return a conditional result: Use a CASE WHEN clause to return Yes if the condition is true and No otherwise.
  4. Output the augmented table: Include the original x, y, and z columns along with the computed triangle column.

Why it works: Each row is evaluated independently. The triangle inequality is a necessary and sufficient condition, so any row passing this check forms a triangle, while any failing it does not.

Python Solution

Since this is an SQL problem, the Python solution would execute the SQL against a database connection. For illustration:

import sqlite3
from typing import List, Tuple

def triangle_judgement(conn: sqlite3.Connection) -> List[Tuple[int, int, int, str]]:
    query = """
    SELECT 
        x,
        y,
        z,
        CASE 
            WHEN x + y > z AND x + z > y AND y + z > x THEN 'Yes'
            ELSE 'No'
        END AS triangle
    FROM Triangle
    """
    cursor = conn.cursor()
    cursor.execute(query)
    result = cursor.fetchall()
    return result

In this implementation, the SQL handles the triangle inequality directly. Python simply executes the query and returns the results as a list of tuples.

Go Solution

In Go, we typically execute SQL queries using the database/sql package:

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
)

type TriangleRow struct {
    X        int
    Y        int
    Z        int
    Triangle string
}

func TriangleJudgement(db *sql.DB) ([]TriangleRow, error) {
    query := `
    SELECT 
        x,
        y,
        z,
        CASE 
            WHEN x + y > z AND x + z > y AND y + z > x THEN 'Yes'
            ELSE 'No'
        END AS triangle
    FROM Triangle
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results []TriangleRow
    for rows.Next() {
        var tr TriangleRow
        if err := rows.Scan(&tr.X, &tr.Y, &tr.Z, &tr.Triangle); err != nil {
            return nil, err
        }
        results = append(results, tr)
    }
    return results, nil
}

In Go, we define a struct to hold each row. We query the database, iterate over the results, and scan each row into the struct. The SQL logic is identical to the Python version.

Worked Examples

For input:

x | y | z
13 | 15 | 30
10 | 20 | 15

Step-by-step:

  1. Row (13, 15, 30):
  • Check 13 + 15 > 30 → 28 > 30 → false
  • Triangle column = No
  1. Row (10, 20, 15):
  • Check 10 + 20 > 15 → 30 > 15 → true
  • Check 10 + 15 > 20 → 25 > 20 → true
  • Check 20 + 15 > 10 → 35 > 10 → true
  • Triangle column = Yes

Output:

x | y | z | triangle
13 | 15 | 30 | No
10 | 20 | 15 | Yes

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row is processed once by the database
Space O(1) No extra space proportional to n; result set returned by query

The reasoning: The SQL query evaluates each row independently. There are no joins or nested operations, so the complexity is linear in the number of rows.

Test Cases

# test cases for Python function
assert triangle_judgement(sqlite3.connect(":memory:")) == []  # empty table

# Table with edge cases
conn = sqlite3.connect(":memory:")
conn.execute("CREATE TABLE Triangle (x int, y int, z int)")
conn.execute("INSERT INTO Triangle VALUES (0, 0, 0)")
conn.execute("INSERT INTO Triangle VALUES (1, 2, 3)")
conn.execute("INSERT INTO Triangle VALUES (2, 2, 3)")
conn.execute("INSERT INTO Triangle VALUES (5, 5, 5)")
conn.commit()
results = triangle_judgement(conn)
assert results == [
    (0, 0, 0, 'No'),      # zero-length sides
    (1, 2, 3, 'No'),      # degenerate triangle
    (2, 2, 3, 'Yes'),     # valid triangle
    (5, 5, 5, 'Yes')      # equilateral triangle
]
Test Why
Empty table Ensures function handles no data
Zero-length sides Checks non-positive side lengths
Degenerate triangle Validates boundary condition x + y = z
Valid triangle Confirms standard positive case
Equilateral triangle Confirms all sides equal are handled

Edge Cases

  1. Zero or negative sides: Any row where one or more sides are zero or negative cannot form a triangle. Our implementation correctly returns No using the triangle inequality checks.
  2. Degenerate triangles: Rows where the sum of two sides equals the third, e.g., (1, 2, 3), do not satisfy > conditions and thus return No, correctly excluding degenerate cases.
  3. Equilateral or isosceles triangles: Cases like (5, 5, 5) or (2, 2, 3) satisfy all three inequalities. The CASE WHEN clause evaluates each condition independently, so such triangles correctly return Yes.