I have given the mentioned problem quite a thought but was not able to come up with a working solution on my own. So I found the following solution, but I want to understand why does it work. Here it is:
class Solution:
def largestPerimeter(self, nums: List[int]) -> int:
# triange in-equality a+b > c
# sum of 2 smallest > largest
nums.sort(reverse=True)
a,b,c = inf,inf,inf
for n in nums:
a, b, c = n, a, b
if a + b > c:
return a+b+c
return 0
Now I will write how I understand this code works and what I do not understand. So. The list is sorted in a descending way with nums.sort(reverse=True). Then a, b, c are given values of infinity each. Then on the first iteration of the for cycle a, b, c are set equal to: a - the highest value from nums; b, c - infinity. Then the program checks if the highest value from nums + infinity is higher than infinity. But isn`t this condition true for any value of a? And even if I understood the condition, why is the output equal to a+b+c = highest value from nums + infinity + infinity? How can this be a valid perimeter for a triangle?
But isn't this condition true for any value of a?
No, that condition is false for any value of a.
In the first iteration, a + b > c will resolve to n0 + inf > inf. Now, n0 + inf returns inf for any integer n0, so inf > inf is false.
Also, in the second iteration, you will have n1 + n0 > inf, which is also always false.
Only in the third iteration, all the infs will be gone and you will start having n2 + n1 > n0, then actual comparisons will happen.
Maybe it would be more clear if the implementation was something like this equivalent code:
nums.sort(reverse=True)
# extract the first 2 elements in a and b,
# and reassign all the remaining back to nums
b, a, *nums = nums
for n in nums:
a, b, c = n, a, b
if a + b > c:
return a+b+c
Please note that, by doing this, you would need to treat the special cases where len(nums) < 3.