976. Largest Perimeter Triangle

Hello, reader 👋🏽 ! Welcome to day 12 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 976. Largest Perimeter Triangle.

🤔 Problem Statement

Given a list of numbers, return the largest possible perimeter of a triangle with non-zero area that can be formed with three numbers. If it's not possible to form any triangle of non-zero area, return 0.

• E.g. [2,1,2] return 5
• E.g. [1,2,1] return 0

💬 Thought Process - Brute Force

• Well, today's question is a walk down memory lane back to geometry classes from school!
• The question says to return the largest possible perimeter for a triangle taking any of the 3 numbers as lengths from the input, provided that the triangle has a non-zero area.

📝 Non-Zero Area of a Triangle

• What does non-zero area of a triangle mean?

  • A triangle given three sides a, b, c, can only be formed if the sum of any two sides is greater than the third side.
  • That is a + b > c.
  • E.g. sides = [2, 1, 2], then 2 < (1+2) and 1 < (2+2).

• It's easy to find any 3 pairs with the brute force approach. We have to iterate over the array with three loops with i, j, k representing indices of side a, b and c.

• Then we'll have to find the largest triplet with nums[i] + nums[k] > nums[j] then return the sum.

👩🏽‍💻 Solution - Brute Force

  int maxPerimeter = 0;
  for(int i = 0; i<n-2; i++) {
    for(int j = i+1; j<n-1; j++) {
      for(int k = j+1; k<n; k++) {
        int sideA = nums[i];
        int sideB = nums[j];
        int sideC = nums[k];
        if(sideA + sideB < sideC) {
          maxPerimeter = Math.max(maxPerimeter, (sideA + sideB + sideC));
        }
      }
    }
  }
  return maxPerimeter;

Time Complexity: O(n^3)
    - n = number of elements
Space Complexity: O(1)

• Although easy the above solution is highly inefficient. So, how can we improve?

💬 Thought Process - Brute Force

• The answer now lies in the fact that we only have to find the largest such perimeter. For that we can choose the largest number and then compare it with the next 2 smaller numbers.
• To find largest set of triplets, we can sort the array.
• Once sorted, we can check for possible triplets from the end of the sorted list: [n-1, n-2, n-3], [n-2,n-3,n-4],... ,[3, 2, 1].
  • Why?
    1. Since we have to find the largest parameter, we can just sort the array and start by picking the 3 largest values. If we find a triplet such that a+b >= c, then we know for sure that this is going to be triplet with largest sum. As the numbers before a,b, and c are smaller.
    2. Let a, b, and c be the largest values at indices n-3, n-2, and n-1 respectively. If we find that a+b <= c, then we know for sure that there can be no other values before a and b (at indices < n-3) where x + y > c where x <= a and y <=b as the array is sorted. Hence we can ignore the number at n-1 index and check for other triplets.

Credits to this reply and explanation. Taken from the discussions in the solution tab.

👩🏽‍💻 Solution - Sorting and Greedy

• Below is the code for the sorted and greedy approach:

class Solution {
    public int largestPerimeter(int[] nums) {
        if(nums == null || nums.length < 3) {
            return 0;
        }
        Arrays.sort(nums);
        int n = nums.length;
        for(int i = n-3; i>=0; i--) {
            int a = nums[i];
            int b = nums[i+1];
            int c = nums[i+2];
            if((a + b) > c) {
                return a + b + c;
            }
        }

        return 0;
    }
}

Time Complexity: O(n logn)
    - n = number of elements in the array
Space Complexity: O(1)

Checkout the code on GitHub for this problem: 976. Largest Perimeter Triangle.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!