Skip to main content

812. Largest Perimeter Triangle

easy

Given an array of positive lengths, find the largest perimeter of a triangle with non-zero area. Sort descending and scan three consecutive lengths — the triangle inequality does the rest.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

Example 1

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

Explanation: You can form a triangle with three side lengths: 2, 1, and 2.

Example 2

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Triangle inequality: a + b > c is required, where c is the longest side.

Hint 2

Sort the array. For any consecutive triple in the sorted order, that triple is the best candidate involving the largest of the three (smaller sides max out the sum).

Hint 3

Walk the sorted array from right to left checking nums[i] + nums[i+1] > nums[i+2] (or equivalently nums[i-2] + nums[i-1] > nums[i]).

Hint 4

First valid triple gives the largest perimeter.

Solution approach

Reveal approach

Sort the array in ascending order. Iterate i from n - 1 down to 2: if nums[i-2] + nums[i-1] > nums[i], return the sum (the perimeter). If no triple satisfies the inequality, return 0. Why consecutive is optimal: if (a, b, c) with a <= b <= c is a triangle, we want to maximize a + b + c subject to a + b > c. For a fixed c, the largest valid (a, b) are the next two largest below c — which are exactly the two values immediately before c in the sorted order. Iterating from the back gives the largest c first; the first valid triple is the maximum. O(n log n) time for the sort, O(1) extra space.

Complexity

Time
O(n log n)
Space
O(1)

Related patterns

  • math
  • sorting
  • greedy

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Largest Perimeter Triangle and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →