algoadvance

Leetcode 976. Largest Perimeter Triangle

Problem Statement

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

Example 2:

Input: nums = [1,2,1]
Output: 0

Clarifying Questions

  1. What is the range of inputs?
    • The array length ranges from 3 to 10^4 and each number ranges from 1 to 10^6.
  2. Can the array contain duplicate numbers?
    • Yes, duplicates are allowed.
  3. What is the desired performance?
    • Ideally, we should aim for an O(n log n) solution due to sorting, as typical constraints can go up to 10^4 numbers.

Strategy

  1. Sort the Array:
    • First, sort the array in non-decreasing order.
  2. Iterate from the End:
    • Iterate over the sorted array from the end towards the beginning. This helps in quickly finding the largest perimeter by checking the largest values first.
  3. Triangle Inequality:
    • For any three sides to form a triangle, the sum of any two sides must be greater than the third one: [ A + B > C ]
    • Therefore, in a sorted array, for the sides nums[i-2], nums[i-1], and nums[i], we only need to check if: [ nums[i-2] + nums[i-1] > nums[i] ]
  4. Return the Perimeter:
    • Return the perimeter of the first valid triangle found by this method. If no such triangle exists, return 0.

Code

import java.util.Arrays;

public class LargestPerimeterTriangle {
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 2; i--) {
            if (nums[i - 2] + nums[i - 1] > nums[i]) {
                return nums[i - 2] + nums[i - 1] + nums[i];
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        LargestPerimeterTriangle lpt = new LargestPerimeterTriangle();
        // Test case 1
        int[] nums1 = {2, 1, 2};
        System.out.println(lpt.largestPerimeter(nums1)); // Output: 5
        
        // Test case 2
        int[] nums2 = {1, 2, 1};
        System.out.println(lpt.largestPerimeter(nums2)); // Output: 0
    }
}

Time Complexity

Overall, the time complexity is O(n log n), which is efficient for the given problem constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI