Largest Perimeter Triangle

Description

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

Solution

Right off the bat two things come to mind:

Sorting in descending order would probably be helpful when looking for the largest

function largestPerimeter(nums) {
  nums.sort((a, b) => b - a);
}

Next!

How in the heck can you tell if three sides make up a triangle?

Some quality research leads to a theorem called basic triangle inequality that provides a simple enough mathematical rule for this:

If x, y, and z are the lengths of the sides of the triangle, with no side being greater than z, then the triangle inequality states that

z <= x + y

Cool! After learning this the sorting makes even more sense as we will always have the largest side as the first item in our array. So if we loop through the array and take the current side, z, and make sure that it is lesser than or equal to the sum of the two that follows, x and y, the first combination of z, x and y for which the statement above is true should be our sides!

function largestPerimeter(nums) {
  nums.sort((a, b) => b - a);

  for (let i = 0; i < nums.length; i++) {
    let z = nums[i],
      x = nums[i + 1],
      y = nums[i + 2];

    if (z <= x + y) {
      return z + x + y;
    }
  }

  return 0;
}

Nope… It passes one of the default test cases but not the other.

Let’s take a look at the failing test’s input: [1,2,1,10]. And it outputs 4 which tells me that it’s the sum of 1, 2 and 1.

After some crude drawing I don’t see how those sides make a triangle. Let’s read that wiki on triangles again.

This statement permits the inclusion of degenerate triangles, but some authors, especially those writing about elementary geometry, will exclude this possibility, thus leaving out the possibility of equality.

Heh, degenerate triangles.

So, a quick read highlights that a degenerate triangle a triangle with zero area. Basically a line. They should have mentioned that in the description.

return *the largest perimeter of a triangle with a non-zero area*

…

-    if (z <= x + y) {
+    if (z < x + y) {

Eureka!

After excluding cases where the largest side z is equal to the sum of x and y all tests are passing and the solution is submitted a few times; averaging the submission results show that the solution is fairly optimised. There might be an advantage in writing a custom sort, but I am satisfied.

Happy coding!