Jobs

Interviews

Discussions

Largest Perimeter Triangle

Easy

Asked by:

8 views

Topics:

ArraysGreedy Algorithms

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.

Example 1:

Input: nums = [2,1,2]
Output: 5
Explanation: You can form a triangle with three side lengths: 1, 2, 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.

Constraints:

3 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁶

Largest Perimeter Triangle

Easy

Asked by:

8 views

Topics:

ArraysGreedy Algorithms

Example 1:

Input: nums = [2,1,2]
Output: 5
Explanation: You can form a triangle with three side lengths: 1, 2, 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.

Constraints:

3 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁶

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the `nums` array? Could they be negative or zero?
What is the size limit of the `nums` array?
If multiple sets of three lengths can form a triangle with the same maximum perimeter, can I return any one of those perimeters?
Are there any constraints on the data type I should use, or should I assume integers are sufficient?
If no triangle can be formed, is returning 0 the only acceptable output, or are there any other acceptable error conditions?

Brute Force Solution

Approach

The brute force approach to finding the largest perimeter triangle from a set of side lengths means we will check every possible combination of three sides. We'll then determine if those three sides can form a valid triangle, and if so, calculate its perimeter.

Here's how the algorithm would work step-by-step:

First, consider every possible group of three side lengths from the given set.
For each group of three, check if the triangle inequality theorem holds. This means that the sum of any two sides must be greater than the third side.
If the triangle inequality theorem holds, then these three sides can form a valid triangle. Calculate the perimeter by adding the lengths of the three sides together.
Keep track of the largest perimeter found so far.
Continue considering every possible group of three sides, repeating the process of checking the triangle inequality theorem and calculating the perimeter if valid.
Once all possible groups have been considered, return the largest perimeter found.

Code Implementation

def largest_perimeter_triangle(side_lengths):
    number_of_sides = len(side_lengths)
    largest_perimeter = 0

    for first_side_index in range(number_of_sides):
        for second_side_index in range(first_side_index + 1, number_of_sides):
            for third_side_index in range(second_side_index + 1, number_of_sides):

                first_side = side_lengths[first_side_index]
                second_side = side_lengths[second_side_index]
                third_side = side_lengths[third_side_index]

                # Triangle inequality theorem: sum of any two sides > third side

                if first_side + second_side > third_side and \
                   first_side + third_side > second_side and \
                   second_side + third_side > first_side:

                    current_perimeter = first_side + second_side + third_side

                    # Keep track of largest valid perimeter

                    if current_perimeter > largest_perimeter:
                        largest_perimeter = current_perimeter

    return largest_perimeter

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n³) – The given algorithm iterates through all possible combinations of three side lengths from the input array of size n. This involves three nested loops, each potentially iterating up to n times. For each such combination, a constant-time check is performed to validate the triangle and calculate the perimeter. Thus, the dominant operation is the threefold iteration, leading to approximately n * n * n operations, which simplifies to O(n³).

Space Complexity

O(1) – The described algorithm iterates through all possible combinations of three sides. It only uses a few variables to store the lengths of the three sides being considered, a variable to hold the current perimeter (if the triangle is valid), and another to store the largest perimeter found so far. These variables require a constant amount of extra space, irrespective of the input size N (the number of side lengths). Thus, the space complexity is O(1).

Optimal Solution

Approach

To find the largest triangle perimeter, we want to quickly find the three longest sides that actually form a triangle. Instead of checking all combinations, we sort the sides and work backwards, making it efficient.

Here's how the algorithm would work step-by-step:

First, organize the side lengths from largest to smallest.
Then, start with the three largest side lengths.
Check if these three sides can form a valid triangle. Remember, the sum of the two shorter sides must be greater than the longest side.
If they can, you've found the triangle with the largest perimeter. Calculate and return the perimeter.
If they can't, move to the next set of three longest sides by discarding the smallest of the current three and including the next largest available side from your sorted list.
Keep repeating this process until you find a valid triangle or run out of sides.
If you can't form a triangle with any combination, return 0.

Code Implementation

def largest_perimeter(nums):    nums.sort(reverse=True)
    for i in range(len(nums) - 2):
        # Iterate, ensuring at least three sides are available
        longest_side = nums[i]
        second_longest_side = nums[i+1]
        shortest_side = nums[i+2]
        # The triangle inequality theorem must hold.
        if second_longest_side + shortest_side > longest_side:
            return longest_side + second_longest_side + shortest_side
    # If no such triangle can be formed, return 0
    return 0

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the input array nums of size n, which takes O(n log n) time. The subsequent while loop iterates at most n-2 times, but each iteration involves only a constant number of comparisons to check the triangle inequality. Therefore, the time complexity of the while loop is O(n). Since O(n log n) dominates O(n), the overall time complexity is O(n log n).

Space Complexity

O(1) – The algorithm sorts the input array in place. Beyond the input array and a few variables used in place for comparison and looping, no auxiliary data structures like temporary lists or hash maps are used. Therefore, the extra memory required is constant and independent of the number of sides (N) in the input array. The space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately since no triangle can be formed.
Input array with less than 3 elements	Return 0 immediately, as a triangle requires at least three sides.
Input array contains negative numbers	Return 0, because side lengths must be positive.
Input array contains zero values	Zero length sides are invalid for triangle formation, handle them normally.
Input array with very large positive integer values that could cause overflow during perimeter calculation	Consider using a larger data type or checking for overflow before returning the perimeter.
Input array with all identical values, forming an equilateral triangle	The solution should correctly calculate the perimeter of the equilateral triangle.
Input array with values that cannot form a valid triangle (e.g., 1, 2, 5)	The solution should return 0 if no combination of three values satisfies the triangle inequality theorem.
Input array already sorted in descending order	The solution needs to handle correctly already sorted input array.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the `nums` array? Could they be negative or zero?
What is the size limit of the `nums` array?
If multiple sets of three lengths can form a triangle with the same maximum perimeter, can I return any one of those perimeters?
Are there any constraints on the data type I should use, or should I assume integers are sufficient?
If no triangle can be formed, is returning 0 the only acceptable output, or are there any other acceptable error conditions?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider every possible group of three side lengths from the given set.
For each group of three, check if the triangle inequality theorem holds. This means that the sum of any two sides must be greater than the third side.
If the triangle inequality theorem holds, then these three sides can form a valid triangle. Calculate the perimeter by adding the lengths of the three sides together.
Keep track of the largest perimeter found so far.
Continue considering every possible group of three sides, repeating the process of checking the triangle inequality theorem and calculating the perimeter if valid.
Once all possible groups have been considered, return the largest perimeter found.

Code Implementation

def largest_perimeter_triangle(side_lengths):
    number_of_sides = len(side_lengths)
    largest_perimeter = 0

    for first_side_index in range(number_of_sides):
        for second_side_index in range(first_side_index + 1, number_of_sides):
            for third_side_index in range(second_side_index + 1, number_of_sides):

                first_side = side_lengths[first_side_index]
                second_side = side_lengths[second_side_index]
                third_side = side_lengths[third_side_index]

                # Triangle inequality theorem: sum of any two sides > third side

                if first_side + second_side > third_side and \
                   first_side + third_side > second_side and \
                   second_side + third_side > first_side:

                    current_perimeter = first_side + second_side + third_side

                    # Keep track of largest valid perimeter

                    if current_perimeter > largest_perimeter:
                        largest_perimeter = current_perimeter

    return largest_perimeter

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, organize the side lengths from largest to smallest.
Then, start with the three largest side lengths.
Check if these three sides can form a valid triangle. Remember, the sum of the two shorter sides must be greater than the longest side.
If they can, you've found the triangle with the largest perimeter. Calculate and return the perimeter.
If they can't, move to the next set of three longest sides by discarding the smallest of the current three and including the next largest available side from your sorted list.
Keep repeating this process until you find a valid triangle or run out of sides.
If you can't form a triangle with any combination, return 0.

Code Implementation

def largest_perimeter(nums):    nums.sort(reverse=True)
    for i in range(len(nums) - 2):
        # Iterate, ensuring at least three sides are available
        longest_side = nums[i]
        second_longest_side = nums[i+1]
        shortest_side = nums[i+2]
        # The triangle inequality theorem must hold.
        if second_longest_side + shortest_side > longest_side:
            return longest_side + second_longest_side + shortest_side
    # If no such triangle can be formed, return 0
    return 0

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately since no triangle can be formed.
Input array with less than 3 elements	Return 0 immediately, as a triangle requires at least three sides.
Input array contains negative numbers	Return 0, because side lengths must be positive.
Input array contains zero values	Zero length sides are invalid for triangle formation, handle them normally.
Input array with very large positive integer values that could cause overflow during perimeter calculation	Consider using a larger data type or checking for overflow before returning the perimeter.
Input array with all identical values, forming an equilateral triangle	The solution should correctly calculate the perimeter of the equilateral triangle.
Input array with values that cannot form a valid triangle (e.g., 1, 2, 5)	The solution should return 0 if no combination of three values satisfies the triangle inequality theorem.
Input array already sorted in descending order	The solution needs to handle correctly already sorted input array.