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 | +----+----+----+----------+
To determine whether three segments can form a triangle, we can directly apply the triangle inequality theorem. For segments with lengths x, y, and z to form a triangle, the following conditions must be met:
x + y > zx + z > yy + z > xIf all three conditions are satisfied, then the segments can form a triangle.
This C program defines a function checkTriangle which checks if three given sides can form a triangle using the triangle inequality theorem. The main function initializes an array of sides, iterates through each set of sides, and calls checkTriangle for each set.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) per triangle check since we only run a constant number of comparisons.
Space Complexity: O(1) since no additional space proportional to input size is used.
In this approach, we first sort the three sides so that we only need to check one inequality condition instead of three. Given sides x, y, and z, sort them to be a ≤ b ≤ c. Then check: a + b > c.
Sorting reduces the number of comparisons and handles the integer sides efficiently when checking validity of the triangle.
Using selection-like sorting, this C program sorts the three side lengths before checking only the most significant triangle inequality condition. The sort function performs simple comparisons and swaps.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) since sorting three items is constant time and checking has a constant cost.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Direct Triangle Inequality Check | Time Complexity: O(1) per triangle check since we only run a constant number of comparisons. |
| Approach 2: Pre-sorting Approach for Inequality Checks | Time Complexity: O(1) since sorting three items is constant time and checking has a constant cost. |
Triangle - Dynamic Programming made Easy - Leetcode 120 • NeetCode • 56,666 views views
Watch 9 more video solutions →Practice Triangle Judgement with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor