976. Largest Perimeter Triangle

Largest Perimeter Triangle

Problem 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.

 

Example 1:

Input: nums = [2,1,2]
Output: 5

Example 2:

Input: nums = [1,2,1]
Output: 0

 

Constraints:

• 3 <= nums.length <= 104
• 1 <= nums[i] <= 106

Approach) Sort

Without loss of generality, say the side lengths of the triangle are a≤b≤c. 

The necessary and sufficient condition for these lengths to form a triangle of the non-zero area is a+b>c.

Say we knew cc already.

There is no reason not to choose the largest possible a and b from the array. 

If a+b>c, then it forms a triangle, otherwise it doesn't.

Algorithm

• This leads to a simple algorithm: Sort the array. 
• For any c in the array, we choose the largest possible a≤b≤c: 
• these are just the two values adjacent to c. 
• If this forms a triangle, we return the answer.

Code:

/**
 * @param {number[]} nums
 * @return {number}
 */
var largestPerimeter = function(nums) {
    nums.sort((a, b) => b - a);
      const N = nums.length - 2;
      for (let i = 0; i < N; i++) {
        if (nums[i] < nums[i + 1] + nums[i + 2]) return nums[i] + nums[i + 1] + nums[i + 2];
      }
      return 0;
};

Runtime: 191 ms, faster than 13.37% of JavaScript online submissions for Largest Perimeter Triangle.
Memory Usage: 45.3 MB, less than 75.97% of JavaScript online submissions for Largest Perimeter Triangle.

Complexity 

Time Complexity
O(NlogN), where N is the length of nums.

Space Complexity
O(1)

Conclusion

That’s all folks! In this post, we solved LeetCode problem #976. Largest Perimeter Triangle

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!