Maximum Perimeter Triangle

See the original problem on HackerRank.

Solutions

This problem simulates the situation when you need some additional “domain knowledge” to find a solution. In this case the domain is “geometry” and you have to find (or recall) the Triangle inequality:

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 terms, for any three sticks \(a, b, c\), the following must be true:

\( a > b + c\) \( b > a + c\) \( c > a + b\)

Since we want the maximum perimeter triangle, we can sort the sticks in descending order and check for each triple of adjacent sticks if the inequality is verified:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int n;
cin >> n;
vector<int> v(n);
copy_n(istream_iterator<int>(cin), n, begin(v));
sort(begin(v), end(v), greater<>{});
for (auto i=0; i<n-2; ++i)
{
    if (v[i+2] + v[i+1] > v[i])
    {
        cout << v[i+2] << " " << v[i+1] << " " << v[i];
        return 0;
    }
}
cout << -1;

Note that we only check:

\( b + c > a\)

since:

\( a > b > c\)

If the former is verified, we know that:

\( a + c > b\)

since \( a > b\)

And \( a + b > c\)

since \( a > c\)

The final cost is \( O(N \cdot log N) \).

Here is a fluent solution in Python:

1
2
3
4

def maximumPerimeterTriangle(sticks):
    sticks = sorted(sticks, reverse=True)
    sticks = zip(sticks, sticks[1:], sticks[2:])
    return next( ([x3,x2,x1] for (x1,x2,x3) in sticks if x3+x2>x1), [-1])