{x}
blog image

Triangle Judgement

Table: Triangle

+-------------+------+
| Column Name | Type |
+-------------+------+
| x           | int  |
| y           | int  |
| z           | int  |
+-------------+------+
In SQL, (x, y, z) is the primary key column for this table.
Each row of this table contains the lengths of three line segments.

 

Report for every three line segments whether they can form a triangle.

Return the result table in any order.

The result format is in the following example.

 

Example 1:

Input: 
Triangle table:
+----+----+----+
| x  | y  | z  |
+----+----+----+
| 13 | 15 | 30 |
| 10 | 20 | 15 |
+----+----+----+
Output: 
+----+----+----+----------+
| x  | y  | z  | triangle |
+----+----+----+----------+
| 13 | 15 | 30 | No       |
| 10 | 20 | 15 | Yes      |
+----+----+----+----------+

Solution Explanation for LeetCode 610: Triangle Judgement

This problem asks us to determine whether three given line segments can form a triangle. The core concept relies on the triangle inequality theorem: the sum of the lengths of any two sides of a triangle must be greater than the length of the third side.

Approach

The solution employs a straightforward approach using a conditional statement (IF in SQL). For each row in the Triangle table representing a set of three sides (x, y, z), we check if the triangle inequality holds for all three combinations of sides:

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

If all three conditions are true, the segments can form a triangle, and we output 'Yes'; otherwise, we output 'No'.

SQL Code (MySQL)

SELECT
    *,
    IF(x + y > z AND x + z > y AND y + z > x, 'Yes', 'No') AS triangle
FROM Triangle;

This SQL query selects all columns from the Triangle table and adds a new column named triangle. The IF function evaluates the three triangle inequality conditions. If all are true, it assigns 'Yes' to the triangle column; otherwise, it assigns 'No'.

Time and Space Complexity Analysis

Time Complexity: O(N), where N is the number of rows in the Triangle table. The query iterates through each row once to perform the checks.

Space Complexity: O(N) in the worst case. This is due to the potential need to store the entire result set which contains the original table and added column. In practice, the space used is likely to be relatively small compared to the input size unless the input is exceptionally large. If we were to only output the triangle column, the space complexity would reduce to O(1) as it only needs to store a single value per row.