Problem

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.

Examples

Example 1

1
2
3

Input: nums = [2,1,2]
Output: 5
Explanation: You can form a triangle with three side lengths: 1, 2, and 2.

Example 2

1
2
3
4
5
6
7

Input: nums = [1,2,1,10]
Output: 0
Explanation: 
You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

Constraints

  • 3 <= nums.length <= 10^4
  • 1 <= nums[i] <= 10^6

Solution

Method 1 – Greedy with Sorting

Intuition

To form a triangle, the sum of any two sides must be greater than the third. Sorting the array allows us to check the largest possible perimeters first by trying the largest three sides and moving down.

Approach

  1. Sort the array in non-increasing order.
  2. Iterate from the largest side down, checking if the sum of the two smaller sides is greater than the largest.
  3. Return the perimeter of the first valid triangle found.
  4. If no valid triangle exists, return 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        sort(nums.rbegin(), nums.rend());
        for (int i = 0; i + 2 < nums.size(); ++i) {
            if (nums[i+1] + nums[i+2] > nums[i])
                return nums[i] + nums[i+1] + nums[i+2];
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9

func largestPerimeter(nums []int) int {
    sort.Sort(sort.Reverse(sort.IntSlice(nums)))
    for i := 0; i+2 < len(nums); i++ {
        if nums[i+1]+nums[i+2] > nums[i] {
            return nums[i] + nums[i+1] + nums[i+2]
        }
    }
    return 0
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        for (int i = nums.length-1; i >= 2; --i) {
            if (nums[i-1] + nums[i-2] > nums[i])
                return nums[i] + nums[i-1] + nums[i-2];
        }
        return 0;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun largestPerimeter(nums: IntArray): Int {
        nums.sortDescending()
        for (i in 0..nums.size-3) {
            if (nums[i+1] + nums[i+2] > nums[i])
                return nums[i] + nums[i+1] + nums[i+2]
        }
        return 0
    }
}
1
2
3
4
5
6
7

class Solution:
    def largestPerimeter(self, nums: list[int]) -> int:
        nums.sort(reverse=True)
        for i in range(len(nums)-2):
            if nums[i+1] + nums[i+2] > nums[i]:
                return nums[i] + nums[i+1] + nums[i+2]
        return 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn largest_perimeter(nums: Vec<i32>) -> i32 {
        let mut nums = nums;
        nums.sort_by(|a, b| b.cmp(a));
        for i in 0..nums.len()-2 {
            if nums[i+1] + nums[i+2] > nums[i] {
                return nums[i] + nums[i+1] + nums[i+2];
            }
        }
        0
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    largestPerimeter(nums: number[]): number {
        nums.sort((a, b) => b - a)
        for (let i = 0; i + 2 < nums.length; ++i) {
            if (nums[i+1] + nums[i+2] > nums[i])
                return nums[i] + nums[i+1] + nums[i+2]
        }
        return 0
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the length of nums. Sorting dominates.
  • 🧺 Space complexity: O(1), if sorting in-place.