Given a list of lists, the task is to find whether a sublist satisfies the triangle inequality. The triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side. In other words, a triangle is valid if sum of its two sides is greater than the third side. If three sides are a, b and c, then three conditions should be met.
a + b > c a + c > b b + c > a
Method #1 : Using List comprehension
Python3
# Python code to find whether a sublist # satisfies the triangle inequality.# List initializationInput = [[1, 3, 1], [4, 5, 6]]# Sorting sublistfor elem in Input: elem.sort()# Using list comprehensionOutput = [(p, q, r) for p, q, r in Input if (p + q)>= r]# Printing outputprint(Output) |
[(4, 5, 6)]
Time Complexity: O(n), where n is the length of the list test_list
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res list
Method #2 : Using Iteration
Python3
# Python code to find whether a sublist# satisfies the triangle inequality.# List initializationInput = [[1, 1, 3], [4, 5, 6]]# Sorting sublist of list of listfor elem in Input: elem.sort()# Checking for triangular inequalityfor elem in Input: if elem[0] + elem[1] > elem[2]: print(elem) |
[4, 5, 6]
Method #3 : Using filter
Another approach you can use is to use the filter function to filter the sublists in the input list that satisfy the triangle inequality.
Here is an example of how you can do this:
Python3
# List initializationInput = [[1, 1, 3], [4, 5, 6]]# Check if the triangle inequality holds for each sublistvalid_sublists = filter(lambda x: x[0] + x[1] > x[2] and x[0] + x[2] > x[1] and x[1] + x[2] > x[0], Input)print(list(valid_sublists))#This code is contributed by Edula Vinay Kumar Reddy |
[[4, 5, 6]]
The time complexity of this approach is O(n), where n is the number of sublists in the input list, because the filter function iterates over each element in the input list and applies the filtering function to it. The space complexity is also O(n), because the valid_sublists list will have a size equal to the number of sublists that satisfy the triangle inequality.
