We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Given any triangle, if a, b, and c are the lengths of the sides, the following is always true:
a + b > c &&
b + c > a &&
c + a > b
Given a sorted array named 'a', if indices x < y < z then a[x] <= a[y] <= a[z] is alway true, which makes a[y] + a[z] > a[x] and a[z] + a[x] > a[y] always true. So to make a valid triangle on top of that, we only need to make sure that one more condition is met:
a[x] + a[y] > a[z] (in which a[x], a[y], a[z] are the three sides and in that order)
From the description, we know we want a[z] to be the largest possible, and given that, a[x] to be the largest possible. What that implies is that they are the last three consecutive elements in the sorted assending array which satisfy a[x] + a[y] > a[z]. (why consecutive indexed elements? because if some a[i-3] + a[i-1] > a[i] or a[i-3] + a[i-2] > a[i] we know a[i-2] + a[i-1] > a[i], because the array is sorted and non-decreasing, and the consecutive elements solution will give you the biggest smallest side if exists)
So we search from the back of the array, from the biggest to the smallest of groups of the three consecutive elements in the array, and check if they satisfy a[x] + a[y] > a[z], if satisfied then break out of the loop and print them, if even when we reached the last possible iteration (the first and smallest element a[0] as a[x], and the opposite condition a[x]+a[y]<=a[z] still passes the check, which means it will never satisfy a[x] + a[y] > a[z] ever, we much now print -1 and return to end the search.)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Maximum Perimeter Triangle
You are viewing a single comment's thread. Return to all comments →
Given any triangle, if a, b, and c are the lengths of the sides, the following is always true:
a + b > c && b + c > a && c + a > b
Given a
sorted
array named 'a', if indicesx < y < z
thena[x] <= a[y] <= a[z]
is alway true, which makesa[y] + a[z] > a[x]
anda[z] + a[x] > a[y]
always true. So to make a valid triangle on top of that, we only need to make sure that one more condition is met:a[x] + a[y] > a[z]
(in whicha[x], a[y], a[z]
are the three sides and in that order)From the description, we know we want a[z] to be the largest possible, and given that, a[x] to be the largest possible. What that implies is that they are the last three consecutive elements in the sorted assending array which satisfy
a[x] + a[y] > a[z]
. (why consecutive indexed elements? because if somea[i-3] + a[i-1] > a[i]
ora[i-3] + a[i-2] > a[i]
we knowa[i-2] + a[i-1] > a[i]
, because the array is sorted and non-decreasing, and the consecutive elements solution will give you the biggest smallest side if exists)So we search from the back of the array, from the biggest to the smallest of groups of the three consecutive elements in the array, and check if they satisfy
a[x] + a[y] > a[z]
, if satisfied then break out of the loop and print them, if even when we reached the last possible iteration (the first and smallest element a[0] as a[x], and the opposite conditiona[x]+a[y]<=a[z]
still passes the check, which means it will never satisfya[x] + a[y] > a[z]
ever, we much now print-1
andreturn
to end the search.)