Problem Description

You are given an integer array nums containing lengths that could potentially form the sides of a triangle. Your task is to find the largest possible perimeter of a triangle that can be formed using any three lengths from the array.

For three lengths to form a valid triangle with non-zero area, they must satisfy the triangle inequality theorem: the sum of any two sides must be greater than the third side. Specifically, if we have three sides a, b, and c where a ≤ b ≤ c, then we need a + b > c.

The perimeter of a triangle is the sum of all three sides: a + b + c.

If no valid triangle can be formed from any combination of three lengths in the array, return 0.

Example scenarios:

• If nums = [2, 1, 2], the three lengths can form a valid triangle (since 1 + 2 > 2), so the perimeter would be 1 + 2 + 2 = 5.
• If nums = [1, 2, 1], these lengths cannot form a valid triangle (after sorting: 1, 1, 2, and 1 + 1 is not greater than 2), so return 0.
• If nums = [3, 2, 3, 4], the best choice would be [3, 3, 4] giving a perimeter of 10.

The key insight is that to maximize the perimeter, we should try to use the largest possible values. By sorting the array and checking from the largest values downward, we can efficiently find the maximum perimeter by checking if three consecutive values (when sorted) can form a valid triangle.

Intuition

To find the largest perimeter, we want to use the three largest possible values that can form a valid triangle. The key observation is that if we sort the array, we should check combinations starting from the largest values and work our way down.

Why does this work? Consider any three sides a ≤ b ≤ c. For these to form a valid triangle, we need a + b > c. This is actually the only condition we need to check because:

• a + c > b is automatically true since c ≥ b
• b + c > a is automatically true since both b ≥ a and c ≥ a

So the critical constraint is whether the two smaller sides can exceed the largest side.

Now, here's the crucial insight: if we have a sorted array and we're checking three consecutive elements nums[i-2], nums[i-1], and nums[i], this gives us the best chance of forming a valid triangle with nums[i] as the largest side. Why? Because nums[i-1] and nums[i-2] are the two largest values that are still smaller than nums[i]. If these two can't sum to more than nums[i], then no other pair of smaller values can either.

By starting from the end of the sorted array and checking consecutive triplets, we ensure that:

1. We find the largest possible perimeter (since we start with the biggest values)
2. We efficiently check only the most promising combinations (consecutive elements after sorting)
3. We can stop as soon as we find a valid triangle, knowing it has the maximum perimeter

This greedy approach works because once we find a valid triangle starting from the largest values, any other valid triangle formed from smaller values will necessarily have a smaller perimeter.

Learn more about Greedy, Math and Sorting patterns.

Solution Approach

The implementation follows a greedy approach with sorting:

1. Sort the array: First, we sort the input array nums in ascending order. This allows us to easily access elements in increasing order and check consecutive triplets.

2. Iterate from largest to smallest: We start from the end of the sorted array (the largest element) and work backwards. The loop runs from index len(nums) - 1 down to index 2 (since we need at least 3 elements to form a triangle).

3. Check triangle validity: For each position i, we check if the three consecutive elements nums[i-2], nums[i-1], and nums[i] can form a valid triangle. Since the array is sorted, we have nums[i-2] ≤ nums[i-1] ≤ nums[i]. We only need to check if nums[i-2] + nums[i-1] > nums[i].

4. Return the perimeter: As soon as we find a valid triangle (the condition nums[i-2] + nums[i-1] > nums[i] is satisfied), we immediately return the perimeter which is nums[i-2] + nums[i-1] + nums[i]. This is guaranteed to be the maximum perimeter because we're checking from the largest values first.

5. Handle the impossible case: If the loop completes without finding any valid triangle, we return 0.

The solution uses the walrus operator := to compute and assign the sum c = nums[i-1] + nums[i-2] in the same expression where it's compared with nums[i]. This makes the code more concise while maintaining readability.

Time Complexity: O(n log n) due to sorting, where n is the length of the array. Space Complexity: O(1) if we don't count the space used by the sorting algorithm (in-place sorting), or O(n) if we consider the space used by the sorting algorithm.

Example Walkthrough

Let's walk through the solution with nums = [3, 6, 2, 3].

Step 1: Sort the array

• Original: [3, 6, 2, 3]
• After sorting: [2, 3, 3, 6]

Step 2: Start from the largest element and check consecutive triplets

Iteration 1 (i = 3):

• Check triplet: [2, 3, 6] (indices 1, 2, 3)
• Triangle inequality: 2 + 3 > 6?
• 5 > 6? No, this is false
• Not a valid triangle, continue

Iteration 2 (i = 2):

• Check triplet: [2, 3, 3] (indices 0, 1, 2)
• Triangle inequality: 2 + 3 > 3?
• 5 > 3? Yes, this is true
• Valid triangle found!

Step 3: Return the perimeter

• Perimeter = 2 + 3 + 3 = 8

The algorithm correctly identifies that [2, 3, 3] forms a valid triangle. Even though [3, 3, 6] would give a larger sum (12), it doesn't form a valid triangle since 3 + 3 = 6 is not greater than 6. By checking from the largest values first and stopping at the first valid triangle, we guarantee we've found the maximum possible perimeter.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the length of the input array nums.

• The nums.sort() operation takes O(n log n) time
• The for loop iterates through the array once in reverse order, which takes O(n) time
• Inside the loop, all operations (array access, addition, comparison) are O(1)
• Therefore, the overall time complexity is dominated by the sorting operation: O(n log n) + O(n) = O(n log n)

Space Complexity: O(1) or O(n) depending on the sorting algorithm implementation.

• If the sorting is done in-place (like Python's Timsort for the worst case), the space complexity could be O(n) in the worst case
• However, if we consider only the extra space used by our algorithm excluding the sorting implementation details, the space complexity is O(1) as we only use a constant amount of extra variables (i and c)
• Most commonly, this would be considered O(1) auxiliary space complexity when analyzing the algorithm itself

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Checking All Possible Combinations Instead of Consecutive Elements

A common mistake is thinking that you need to check all possible combinations of three elements from the sorted array, leading to an O(n³) solution:

Incorrect Approach:

def largestPerimeter(self, nums: List[int]) -> int:
    nums.sort()
    max_perimeter = 0
    # Unnecessarily checking all combinations
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            for k in range(j + 1, len(nums)):
                if nums[i] + nums[j] > nums[k]:
                    max_perimeter = max(max_perimeter, nums[i] + nums[j] + nums[k])
    return max_perimeter

Why it's wrong: This approach is inefficient and unnecessary. Once the array is sorted, if three consecutive elements can't form a triangle, then replacing the smallest element with an even smaller one will never form a valid triangle.

Correct Solution: Only check consecutive triplets from the sorted array, as shown in the original solution.

2. Incorrect Triangle Inequality Check

Another pitfall is checking all three triangle inequalities when only one is necessary after sorting:

Incorrect Approach:

def largestPerimeter(self, nums: List[int]) -> int:
    nums.sort()
    for i in range(len(nums) - 1, 1, -1):
        a, b, c = nums[i-2], nums[i-1], nums[i]
        # Checking all three inequalities (unnecessary)
        if a + b > c and b + c > a and a + c > b:
            return a + b + c
    return 0

Why it's wrong: While not technically incorrect, it's redundant. When a ≤ b ≤ c (sorted order), if a + b > c is true, then the other two inequalities (b + c > a and a + c > b) are automatically satisfied since c is the largest side.

Correct Solution: Only check nums[i-2] + nums[i-1] > nums[i] after sorting.

3. Starting Iteration from the Wrong End

Some might iterate from the beginning of the sorted array instead of the end:

Incorrect Approach:

def largestPerimeter(self, nums: List[int]) -> int:
    nums.sort()
    # Starting from smallest elements
    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

Why it's wrong: This finds the minimum valid perimeter, not the maximum. Since we want the largest perimeter, we should start checking from the largest elements.

Correct Solution: Iterate from len(nums) - 1 down to 2 to check the largest possible triangles first.