algoadvance

Leetcode 976. Largest Perimeter Triangle

Problem Statement

Given an array of positive integers 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.

Clarifying Questions

  1. Range of nums Array: What is the range of values for the length of the array nums?
    • Answer: According to LeetCode, the length of nums will be between 3 and 10,000.
  2. Range of Elements in nums: What is the range of each element in nums?
    • Answer: Each element in nums will be a positive integer less than or equal to 10^6.
  3. Handling Duplicates: Is it possible to have duplicate lengths in the nums array?
    • Answer: Yes, duplicates are allowed.

Strategy

  1. Sorting: First, sort the nums array in non-decreasing order.
  2. Triangle Inequality Theorem: To form a triangle with sides a, b, and c, the sum of any two sides must be greater than the third side.
  3. Iterating: Start checking from the end of the sorted array and look for the largest triplet that satisfies the triangle inequality. Specifically, if the array after sorting is a ≤ b ≤ c, then a + b > c must hold to form a triangle.
  4. Return: Return the perimeter of the first valid triangle found; if none is found, return 0.

Time Complexity

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int largestPerimeter(std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        for (int i = nums.size() - 1; i >= 2; --i) {
            if (nums[i-1] + nums[i-2] > nums[i]) {
                return nums[i] + nums[i-1] + nums[i-2];
            }
        }
        return 0;
    }
};

Explanation

  1. Sorting: The vector nums is sorted in non-decreasing order.
  2. Triangle Formation: Starting from the largest possible side (i from the end of the sorted array), check if the largest side can form a triangle with the two preceding sides. The check nums[i-1] + nums[i-2] > nums[i] ensures the triangle inequality theorem is satisfied.
  3. Return Perimeter: If a valid triangle is found, return its perimeter. If no valid triangle is found by the end of the loop, return 0.

This approach ensures that we get the largest perimeter triangle efficiently.

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