Largest Perimeter Triangle

🏠 ⬅️ ➡️

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 <= 104
  • 1 <= nums[i] <= 106
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 3
    integer, dimension(n) :: nums
    integer :: i, j, k, max_perimeter

    ! Examples
    nums = [2, 1, 2]
    write (*, '(A, I0)') 'Example 1: ', largestPerimeter(nums)
    nums = [1, 2, 1, 10]
    write (*, '(A, I0)') 'Example 2: ', largestPerimeter(nums)

contains

    function largestPerimeter(nums) result(max_perimeter)
        implicit none
        integer, intent(in) :: nums(:)
        integer :: i, j, k, perimeter
        logical :: found

        max_perimeter = 0
        do i = 1, size(nums) - 2
            do j = i + 1, size(nums) - 1
                do k = j + 1, size(nums)
                    perimeter = nums(i) + nums(j) + nums(k)
                    if (perimeter > max_perimeter .and. &
                        nums(i) * nums(j) < nums(k)) then
                        max_perimeter = perimeter
                    end if
                end do
            end do
        end do
    end function largestPerimeter
end program main
❌ Compiled
❌ Executed
❌ Correct 
module largest_triangle_perimeter
    implicit none
    private
    public :: largest_triangle_perimeter

contains

    function largest_triangle_perimeter(nums) result(largest_perimeter)
        implicit none
        integer, intent(in) :: nums(:)
        integer :: largest_perimeter
        integer :: i, j, k
        integer :: a, b, c

        largest_perimeter = 0

        ! Iterate over all possible combinations of three array elements
        do i = 1, size(nums) - 2
            do j = i + 1, size(nums) - 1
                do k = j + 1, size(nums)
                    a = nums(i)
                    b = nums(j)
                    c = nums(k)

                    ! Check if the three sides form a triangle
                    if (a**2 + b**2 >= c**2 .and. b**2 + c**2 >= a**2 .and. c**2 + a**2 >= b**2) then
                        ! Check if the triangle has a non-zero area
                        if (a + b > c .and. b + c > a .and. c + a > b) then
                            largest_perimeter = max(largest_perimeter, a + b + c)
                        end if
                    end if
                end do
            end do
        end do
    end function largest_triangle_perimeter
end module largest_triangle_perimeter

program test_largest_triangle_perimeter
    use largest_triangle_perimeter
    implicit none
    integer, parameter :: nums1(3) = [2, 1, 2]
    integer, parameter :: nums2(4) = [1, 2, 1, 10]
    integer, parameter :: nums3(5) = [3, 4, 5, 6, 7]
    integer, parameter :: nums4(10) = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    integer :: largest_perimeter

    largest_perimeter = largest_triangle_perimeter(nums1)
    write (*,*) "Largest perimeter of a triangle with non-zero area from nums1:", largest_perimeter

    largest_perimeter = largest_triangle_perimeter(nums2)
    write (*,*) "Largest perimeter of a triangle with non-zero area from nums2:", largest_perimeter

    largest_perimeter = largest_triangle_perimeter(nums3)
    write (*,*) "Largest perimeter of a triangle with non-zero area from nums3:", largest_perimeter

    largest_perimeter = largest_triangle_perimeter(nums4)
    write (*,*) "Largest perimeter of a triangle with non-zero area from nums4:", largest_perimeter
end program test_largest_triangle_perimeter
🌐 Data from online sources 
def min_area_rect(points):
    point_set = {(x, y) for x, y in points}
    min_area = float('inf')

    for p1 in point_set:
        for p2 in point_set:
            if p1[0] != p2[0] and p1[1] != p2[1]:
                if (p1[0], p2[1]) in point_set and (p2[0], p1[1]) in point_set:
                    min_area = min(min_area, abs((p1[0] - p2[0]) * (p1[1] - p2[1])))

    return min_area if min_area != float('inf') else 0

1. Convert the given points into a set for efficient lookups.
  1. Initialize min_area to an infinitely large value initially.
  2. Iterate through each pair of distinct points p1 and p2 in the set, and check if two other points p3 and p4 exist such that p3.x = p1.x, p3.y = p2.y, p4.x = p2.x, p4.y = p1.y.
  3. If such points exist, calculate the area between p1 and p2 and update min_area with the minimum value between current min_area and calculated area.
  4. After the iteration, if min_area still holds the initial value (indicating no rectangles were found), return 0; otherwise, return the min_area.
🌐 Data from online sources 
#include <set>
#include <vector>

double minAreaRect(std::vector<std::vector<int>>& points) {
    std::set<std::pair<int, int>> point_set;
    for (const auto& point : points) {
        point_set.emplace(point[0], point[1]);
    }

    double min_area = INT32_MAX;
    for (const auto& p1 : point_set) {
        for (const auto& p2 : point_set) {
            if (p1.first != p2.first && p1.second != p2.second) {
                if (point_set.count({p1.first, p2.second}) && point_set.count({p2.first, p1.second})) {
                    min_area = std::min(min_area, abs((p1.first - p2.first) * (p1.second - p2.second)));
                }
            }
        }
    }

    return min_area == INT32_MAX ? 0 : min_area;
}

1. Convert the given points into a set for efficient lookups.
  1. Initialize min_area to an infinitely large value initially.
  2. Iterate through each pair of distinct points p1 and p2 in the set, and check if two other points p3 and p4 exist such that p3.x = p1.x, p3.y = p2.y, p4.x = p2.x, p4.y = p1.y.
  3. If such points exist, calculate the area between p1 and p2 and update min_area with the minimum value between current min_area and calculated area.
  4. After the iteration, if min_area still holds the initial value (indicating no rectangles were found), return 0; otherwise, return the min_area.