Skip to content

← leetcode

Largest Perimeter Triangle

· Easy

LeetCode problem 976

You can sort nums from smallest to largest...

sort(nums.begin(), nums.end());

... and then iterate backwards, with index i, checking if the last 3 elements (i, i-1 & i-2) fit the triangle inequality. If those 3 elements do not satisfy the triangle inequality, then no combination of elements with i as the largest side will form a valid triangle.

for (int i = nums.size()-1; i >= 2; --i) {
    if (nums[i] < nums[i-1] + nums[i-2]) {
        return nums[i] + nums[i-1] + nums[i-2];
    }
}
return 0;

code

class solution {
public:
    int largestperimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = nums.size()-1; i >= 2; --i) {
            if (nums[i] < nums[i-1] + nums[i-2]) {
                return nums[i] + nums[i-1] + nums[i-2];
            }
        }
        return 0;
    }
};

complexity

  • Time: O(n log(n)) where n denotes the number of elements inside of nums
  • Space: O(1)

time taken

  • 3 minutes and 25 seconds