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 Sam K., 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

More Math practice problems

See all Math problems →