Maximum Area of Longest Diagonal Rectangle

Difficulty: Easy | Acceptance: 45.90% | Paid: No Topics: Array

You are given a 2D array dimensions where dimensions[i] = [length_i, width_i] represents the length and width of the ith rectangle.

The length of the diagonal of the ith rectangle is sqrt(length_i^2 + width_i^2).

Return the area of the rectangle having the longest diagonal. If there are multiple rectangles with the same longest diagonal, return the area of the rectangle having the maximum area.

• Examples
• Constraints
• Approach 1: Iterative Comparison
• Approach 2: Sorting

Examples

Example 1:

Input: dimensions = [[9,3],[8,6]]
Output: 48
Explanation:
For rectangle 1: length = 9, width = 3, diagonal = sqrt(9² + 3²) = sqrt(90), area = 27.
For rectangle 2: length = 8, width = 6, diagonal = sqrt(8² + 6²) = sqrt(100), area = 48.
The longest diagonal is sqrt(100), so we return the area of rectangle 2, which is 48.

Example 2:

Input: dimensions = [[3,4],[4,3]]
Output: 12
Explanation:
Both rectangles have a diagonal of sqrt(3² + 4²) = 5.
Since both have the same longest diagonal, we return the maximum area, which is 12.

Constraints

- 1 <= dimensions.length <= 100
- dimensions[i].length == 2
- 1 <= dimensions[i][0], dimensions[i][1] <= 100

Approach 1: Iterative Comparison

Intuition We can iterate through the list of rectangles once. For each rectangle, we calculate the squared length of the diagonal to avoid floating-point precision issues. We keep track of the maximum diagonal squared found so far and the corresponding area. If we find a rectangle with a larger diagonal, we update our maximums. If we find a rectangle with the same diagonal length but a larger area, we update the area.

Steps

• Initialize max_diag_sq to -1 and max_area to 0.
• Iterate through each rectangle in the dimensions array.
• For each rectangle, extract length and width.
• Calculate diag_sq as length * length + width * width.
• Calculate area as length * width.
• If diag_sq is greater than max_diag_sq, update max_diag_sq to diag_sq and max_area to area.
• Else if diag_sq is equal to max_diag_sq and area is greater than max_area, update max_area to area.
• Return max_area.

class Solution:
    def areaOfMaxDiagonal(self, dimensions: list[list[int]]) -> int:
        max_diag_sq = -1
        max_area = 0
        for l, w in dimensions:
            d = l * l + w * w
            a = l * w
            if d > max_diag_sq:
                max_diag_sq = d
                max_area = a
            elif d == max_diag_sq:
                if a > max_area:
                    max_area = a
        return max_area

Complexity

• Time: O(N), where N is the number of rectangles. We iterate through the list once.
• Space: O(1), as we only use a few variables to store the maximums.
• Notes: This is the most optimal approach as it requires a single pass and constant extra space.

Approach 2: Sorting

Intuition We can sort the array of rectangles based on two criteria: primarily by the squared length of the diagonal in descending order, and secondarily by the area in descending order. After sorting, the first element in the array will be the rectangle with the longest diagonal (and the largest area if there are ties). We simply return its area.

Steps

• Sort the dimensions array using a custom comparator.
• The comparator should first compare the squared diagonal ($l^2 + w^2$). If they are different, sort in descending order.
• If the squared diagonals are the same, compare the area ($l \times w$) and sort in descending order.
• Return the area of the first rectangle in the sorted array.

class Solution:
    def areaOfMaxDiagonal(self, dimensions: list[list[int]]) -> int:
        # Sort by diagonal squared (desc), then by area (desc)
        dimensions.sort(key=lambda x: (x[0]*x[0] + x[1]*x[1], x[0]*x[1]), reverse=True)
        return dimensions[0][0] * dimensions[0][1]

Complexity

• Time: O(N log N), due to the sorting algorithm.
• Space: O(1) or O(N), depending on the sorting algorithm’s implementation (e.g., Timsort in Python uses O(N), in-place sort in C++ uses O(log N) stack space).
• Notes: While concise, this approach is less efficient than the iterative comparison for large inputs due to the sorting overhead.