Domain 1EasyCORE

Largest Perimeter Triangle

The problem asks us to find the largest perimeter of a triangle that can be formed from three lengths given in an integer array `nums`. The triangle must have a non-zero area, which means it must satisfy the triangle inequality theorem: for any three sides a, b, and c (where a <= b <= c), the sum of the two smaller sides must be greater than the largest side (a + b > c). If no such triangle can be formed, we return 0.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math#Sort

976. Largest Perimeter Triangle

Model: qwen2.5-coder:14b
Topics: Math,Sort
FAANG asked: 0
Acceptance rate: 59.3%


Problem Breakdown

The problem asks us to find the largest perimeter of a triangle that can be formed from three lengths given in an integer array nums. The triangle must have a non-zero area, which means it must satisfy the triangle inequality theorem: for any three sides (a), (b), and (c) (where (a \leq b \leq c)), the sum of the two smaller sides must be greater than the largest side ((a + b > c)). If no such triangle can be formed, we return 0.

Inputs:

  • An integer array nums where each element represents a potential side length of a triangle.
  • The length of nums is between 3 and (10^4).
  • Each element in nums is between 1 and (10^6).

Outputs:

  • An integer representing the largest perimeter of a valid triangle, or 0 if no such triangle exists.

Implicit Constraints/Edge Cases:

  • The array must have at least three elements.
  • All elements are positive integers.
  • We need to consider the possibility that no combination of three sides can form a valid triangle.

Intuition

A brute-force approach would involve checking all possible combinations of three sides from the array, which would result in a time complexity of (O(n^3)). This is inefficient given the constraints.

The key insight is to leverage sorting and the triangle inequality theorem. By sorting the array in descending order, we can start checking from the largest possible perimeter (sum of the first three elements) and move downwards. This way, as soon as we find a valid combination that satisfies the triangle inequality, we have found the largest perimeter.

Approach

  1. Sort the Array: Sort the array nums in descending order.
  2. Iterate through the Array: Iterate through the sorted array and check each triplet of consecutive elements to see if they satisfy the triangle inequality theorem.
  3. Return the Perimeter: As soon as a valid triplet is found, return the sum of these three sides as the largest perimeter.
  4. Handle No Valid Triangle: If no valid triplet is found after checking all possibilities, return 0.

Complexity Analysis

  • Time Complexity: (O(n \log n)) due to the sorting step. The subsequent iteration through the array is (O(n)).
  • Space Complexity: (O(1)) as we are not using any additional data structures that scale with input size.

Solution

def largestPerimeter(nums):
    nums.sort(reverse=True)
    for i in range(len(nums) - 2):
        if nums[i] < nums[i + 1] + nums[i + 2]:
            return nums[i] + nums[i + 1] + nums[i + 2]
    return 0

Edge Cases Handled

  • All elements are the same: The sorted array will have all equal elements, and the first triplet will satisfy the triangle inequality.
  • No valid triangle possible: If no triplet satisfies the triangle inequality, the function returns 0.
  • Array with minimum length (3): The function correctly handles the smallest possible input size.