Triangle Judgement

Difficulty: Easy | Acceptance: 74.70% | Paid: No Topics: Database

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.

• Examples
• Constraints
• Approach 1: Direct Conditional Check
• Approach 2: Sorting Optimization

Examples

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      |
+----+----+----+----------+

Constraints

The input table will have at least 1 row.
x, y, z are positive integers.

Approach 1: Direct Conditional Check

Intuition For three lengths to form a triangle, the sum of any two sides must be strictly greater than the third side. We can check all three conditions directly.

Steps

• Iterate through each row of the input data.
• Extract the three side lengths x, y, and z.
• Check if x + y > z, x + z > y, and y + z > x.
• If all conditions are met, the result is “Yes”, otherwise “No”.

from typing import List

class Solution:
    def triangleJudgement(self, triangle: List[List[int]]) -> List[List[str]]:
        res = []
        for x, y, z in triangle:
            if x + y > z and x + z > y and y + z > x:
                res.append([str(x), str(y), str(z), "Yes"])
            else:
                res.append([str(x), str(y), str(z), "No"])
        return res

Complexity

• Time: O(N), where N is the number of rows. We perform a constant amount of work for each row.
• Space: O(N) to store the result list.
• Notes: This is the most straightforward approach and is highly efficient for this problem.

Approach 2: Sorting Optimization

Intuition If we sort the three side lengths such that a ≤ b ≤ c, the triangle inequality theorem simplifies. We only need to check if a + b > c, because a + c > b and b + c > a will always be true if c is the largest side.

Steps

• Iterate through each row.
• Sort the three values x, y, and z.
• Check if the sum of the two smallest numbers is greater than the largest number.
• Return “Yes” or “No” accordingly.

from typing import List

class Solution:
    def triangleJudgement(self, triangle: List[List[int]]) -> List[List[str]]:
        res = []
        for x, y, z in triangle:
            sides = sorted([x, y, z])
            if sides[0] + sides[1] > sides[2]:
                res.append([str(x), str(y), str(z), "Yes"])
            else:
                res.append([str(x), str(y), str(z), "No"])
        return res

Complexity

• Time: O(N * 3 log 3) which simplifies to O(N). Sorting 3 elements is a constant time operation.
• Space: O(N) for the result, plus O(1) auxiliary space for sorting (since the array size is fixed at 3).
• Notes: While theoretically the same asymptotic complexity, the constant factor is slightly higher due to sorting, but it offers a cleaner logical check.